深度为k的完全二叉树至少有___个结点,至多有___个结点。为什么

发布网友 发布时间：2023-07-27 16:19

我来回答

共4个回答

热心网友 时间：2024-10-16 16:51

至少有2的（k-1）次方个节点
最多有（2的k次方）-1个节点

看一下下面的知识：
一棵深度为K且有2的K次方减1个结点的二叉树称为满二叉树。
深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至N的结点一一对应，称之为完全二叉树。
0 0 0
/ \ / \ / \
0 0 0 0 0 0
/ \ / \ / / \
0 0 0 0 0 0 0
(1) (2) (3)
1是满二叉树，也是完全二叉树。
2是完全二叉树。
3非完全二叉树。

简单的讲，将节点按层次从1-n编号：
1
/ \
2 3
/ \ / \
4 5 6 7
... ... ... ...

缺少的节点只能是大号的，
即：如果n号节点存在，则1到n-1号节点必定存在，
同样，若n号节点不存在，则n+1号及更大号的节点也必定不存在

热心网友 时间：2024-10-16 16:51

至少有2的（k-1）次方个节点
最多有（2的k次方）-1个节点
看一下下面的知识：
一棵深度为k且有2的k次方减1个结点的二叉树称为满二叉树.
深度为k的,有n个结点的二叉树,当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应,称之为完全二叉树.
0
0
0
/
\
/
\
/
\
0
0
0
0
0
0
/
\
/
\
/
/
\
0
0
0
0
0
0
0
(1)
(2)
(3)
1是满二叉树,也是完全二叉树.
2是完全二叉树.
3非完全二叉树.
简单的讲,将节点按层次从1-n编号：
1
/
\
2
3
/
\
/
\
4
5
6
7
...
...
...
...
缺少的节点只能是大号的,
即：如果n号节点存在,则1到n-1号节点必定存在,
同样,若n号节点不存在,则n+1号及更大号的节点也必定不存在

热心网友 时间：2024-10-16 16:52

至少有2的（k-1）次方个节点
最多有（2的k次方）-1个节点
看一下下面的知识：
一棵深度为K且有2的K次方减1个结点的二叉树称为满二叉树。
深度为K的，有N个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至N的结点一一对应，称之为完全二叉树。
0
0
0
/
\
/
\
/
\
0
0
0
0
0
0
/
\
/
\
/
/
\
0
0
0
0
0
0
0
(1)
(2)
(3)
1是满二叉树，也是完全二叉树。
2是完全二叉树。
3非完全二叉树。
简单的讲，将节点按层次从1-n编号：
1
/
\
2
3
/
\
/
\
4
5
6
7
...
...
...
...
缺少的节点只能是大号的，
即：如果n号节点存在，则1到n-1号节点必定存在，
同样，若n号节点不存在，则n+1号及更大号的节点也必定不存在

热心网友 时间：2024-10-16 16:52

至少有有K个结点，也就是每棵树只有一个子树；
最多有（2的K次方-1）个结点，也就是满二叉树。