2024年4月7日发(作者:考潍)
1.
设一棵完全二叉树共有
699
个结点,则在该二叉树中的叶子结点数?
1
根据
“
二叉树的第
i
层至多有
2^(i − 1)
个结点;深度为
k
的二叉树至多有
2^k − 1
个结点;
个结点(根结点的深度为
1
)
”
这个性质:
这个性质:
因为
2^9-1 < 699 < 2^10-1 ,
所以这个完全二叉树的深度是
10
,前
9
层是一个满
二叉树,
二叉树,
这样的话,前九层的结点就有
这样的话,
前九层的结点就有
2^9-1=511
个;而第九层的结点数是
个;
而第九层的结点数是
2^(9-1)=256
所以第十层的叶子结点数是
699-511=188
个;
个;
现在来算第九层的叶子结点个数。
现在来算第九层的叶子结点个数。
由于第十层的叶子结点是从第九层延伸的,所以应该去掉第九层中还有子树的结
点。因为第十层有
188
个,所以应该去掉第九层中的
188/2=94
个;
个;
所以,第九层的叶子结点个数是256-94=162,加上第十层有
256-94=162
,加上第十层有188个,最后结果
是350个
2
完全二叉树:若二叉树中最多只有最下面两层的结点的度可以小于
2
,并且最
下面一层的结点(叶结点)
下面一层的结点
(叶结点)都依次排列在该层最左边的位置上,
(叶结点)
都依次排列在该层最左边的位置上,这样的二叉树为
都依次排列在该层最左边的位置上,
这样的二叉树为
完全二叉树。
完全二叉树。
比如图:
比如图:
完全二叉树除叶结点层外的所有结点数(叶结点层以上所有结点数)为奇数,
此题中,
699
是奇数,叶结点层以上的所有结点数为保证是奇数,则叶结点数必
是偶数,这样我们可以立即选出答案为
B
!
如果完全二叉树的叶结点都排满了,则是满二叉树,
如果完全二叉树的叶结点都排满了,
则是满二叉树,易得满二叉树的叶结点数是
其以上所有层结点数
+1
比如图:
比如图:
此题的其实是一棵满二叉树,我们根据以上性质,699+1=700,
699+1=700
,700/2=350,即
700/2=350
,即
叶结点数为350,叶结点层以上所有结点数为
350
,叶结点层以上所有结点数为350-1=349。
350-1=349
。
3
完全二叉树中,只存在度为
2
的结点和度为
0
的结点,而二叉树的性质中有一条是:
n0=n2+1
;
n0
指度为
0
的结点,即叶子结点,
n2
指度为
2
的结点,所以
2n2+1=699 n2=349
;
n0=350
2.
在一棵二叉树上第
5
层的结点数最多是多少
一棵二叉树,如果每个结点都是是满的,那么会满足
2^(k-1)1
。
所以第
5
层至多有
2^(5-1)=16
个结点!
个结点!
3.
在深度为
5
的满二叉树中,叶子结点的个数为
答案是
16 ~
叶子结点就是没有后件的结点
~
说白了
~
就是二叉树的最后一层
~
深度为
K
的二叉树
~
最多有
2^k-1
个结点
~
最多有
2^(k-1)
个结点
~
所以此题
~
最多有
2^5-1=31
个结点
~
最多有
2^(5-1)=16
个叶子结点
~
4.
某二叉树中度为
2
的结点有
18
个,则该二叉树中有几个叶子结点?
结点的度是指树中每个结点具有的子树个数或者说是后继结点数。
题中的度为
2
是说具有的
2
个子树的结点;
个子树的结点;
二叉树有个性质:二叉树上叶子结点数等于度为
2
的结点数加
1
。
5.
在深度为
7
的满二叉树中,度为
2
的结点个数为多少,
就是第一层只有一个节点,他有两个子节点,第二层有两个节点,他们也都有两个子节点
就是第一层只有一个节点,他有两个子节点,第二层有两个节点,他们也都有两个子节点
以此类推,所以到第
6
层,就有
2
的
5
次方个节点,他们都有两个子节点
次方个节点,他们都有两个子节点
最后第
7
层都没有子节点了。因为是深度为
7
的。
的。
所以就是
1+2+4+8+16+32
了
2
深度为
1
的时候有
0
个
深度为
2
的时候有
1
个
深度为
3
的时候有
3
个
深度为
4
的时候有
7
个
....
深度为
n
的时候有(
2
的
n-1
次方减
1
)个
)个
6.
一棵二叉树中共有
70
个叶子结点与
80
个度为
1
的结点,则该二叉树中的总结点
数为?
假设
n
表示二叉树的所有结点数,
n0
表示度为
0
的结点
(
叶子结点
)
,
n1
表示度
为
1
的结点,
n2
表示度为
2
的结点,由二叉树的性质有:
的结点,由二叉树的性质有:
n0 = n2 + 1
已知
n0 = 70
,
则
n2 = n0 -1 = 69
而
n = n0 + n1 + n2
= 70 + 80 + 69
= 219
总结点数 n=70+80+70-1=219
总结点数
n=70+80+70-1=219
2解:对任一二叉树
解:对任一
二叉树,如果其叶子结点
,如果其
叶子结点为n0,度为
n0
,度为1的结点数为n1,度为
n1,
度为2的结
点数为n2,则
n2
,则n0=n2+1;
然后由
然后由n=n0+n1+n2①即可得出。(n
n=n0+n1+n2①即可得出。
(n为结点总数)
为结点总数
)
证明上一结论:由二叉树的特点可知,除了
证明上一结论:由二叉树的特点可知,除了根结点外,所有的结点都是由一
个分支引出来的,因此分支数为A=n-1,而二叉树中的分支都是由度为
A=n-1,
而二叉树中的分支都是由度为1和度为2
的结点发出的,因此有A=n1+2*n2,于是
A=n1+2*n2,
于是A=n-1=n1+2*n2,得到:n=n1+2*n2+1②
A=n-1=n1+2*n2,
得到:n=n1+2*n2+1②
得到:n=n1+2*n2+1②
由①与②可得:
由①与②可得:n0=n2+1
由①与②可得:
n0=n2+1
则该二叉树共有几个结点
7.
某二叉树有
5
个度为
2
的结点和
3
个度为
1
的结点,
二叉树性质:终端结点(叶子节点)个数
n0
=
度为
2
的节点(有
2
个孩子)
个数
n2 + 1
即
n0 = n2 + 1
。
所以本题有:叶子节点个数 ,
所以本题有:叶子节点个数
= 5 + 1 = 6
度为
1
的结点个数 ,
的结点个数
= 3
度为
2
的结点个数 ,
的结点个数
= 5
所以总个数
所以总个数 = 6 + 3 + 5 = 14
所以总个数
= 6 + 3 + 5 = 14
2对任何一棵二叉树
T
,如果其终端结点数为
n0
,度为
2
的结点数为
n2
,则
n0
= n2 + 1
故叶子结点数(即度为
0
的结点)为
5+1=6
二叉树的结点数为
n=n0+n1+n2
所以该二叉树的结点为:
5+3+6=14
|
2024年4月7日发(作者:考潍)
1.
设一棵完全二叉树共有
699
个结点,则在该二叉树中的叶子结点数?
1
根据
“
二叉树的第
i
层至多有
2^(i − 1)
个结点;深度为
k
的二叉树至多有
2^k − 1
个结点;
个结点(根结点的深度为
1
)
”
这个性质:
这个性质:
因为
2^9-1 < 699 < 2^10-1 ,
所以这个完全二叉树的深度是
10
,前
9
层是一个满
二叉树,
二叉树,
这样的话,前九层的结点就有
这样的话,
前九层的结点就有
2^9-1=511
个;而第九层的结点数是
个;
而第九层的结点数是
2^(9-1)=256
所以第十层的叶子结点数是
699-511=188
个;
个;
现在来算第九层的叶子结点个数。
现在来算第九层的叶子结点个数。
由于第十层的叶子结点是从第九层延伸的,所以应该去掉第九层中还有子树的结
点。因为第十层有
188
个,所以应该去掉第九层中的
188/2=94
个;
个;
所以,第九层的叶子结点个数是256-94=162,加上第十层有
256-94=162
,加上第十层有188个,最后结果
是350个
2
完全二叉树:若二叉树中最多只有最下面两层的结点的度可以小于
2
,并且最
下面一层的结点(叶结点)
下面一层的结点
(叶结点)都依次排列在该层最左边的位置上,
(叶结点)
都依次排列在该层最左边的位置上,这样的二叉树为
都依次排列在该层最左边的位置上,
这样的二叉树为
完全二叉树。
完全二叉树。
比如图:
比如图:
完全二叉树除叶结点层外的所有结点数(叶结点层以上所有结点数)为奇数,
此题中,
699
是奇数,叶结点层以上的所有结点数为保证是奇数,则叶结点数必
是偶数,这样我们可以立即选出答案为
B
!
如果完全二叉树的叶结点都排满了,则是满二叉树,
如果完全二叉树的叶结点都排满了,
则是满二叉树,易得满二叉树的叶结点数是
其以上所有层结点数
+1
比如图:
比如图:
此题的其实是一棵满二叉树,我们根据以上性质,699+1=700,
699+1=700
,700/2=350,即
700/2=350
,即
叶结点数为350,叶结点层以上所有结点数为
350
,叶结点层以上所有结点数为350-1=349。
350-1=349
。
3
完全二叉树中,只存在度为
2
的结点和度为
0
的结点,而二叉树的性质中有一条是:
n0=n2+1
;
n0
指度为
0
的结点,即叶子结点,
n2
指度为
2
的结点,所以
2n2+1=699 n2=349
;
n0=350
2.
在一棵二叉树上第
5
层的结点数最多是多少
一棵二叉树,如果每个结点都是是满的,那么会满足
2^(k-1)1
。
所以第
5
层至多有
2^(5-1)=16
个结点!
个结点!
3.
在深度为
5
的满二叉树中,叶子结点的个数为
答案是
16 ~
叶子结点就是没有后件的结点
~
说白了
~
就是二叉树的最后一层
~
深度为
K
的二叉树
~
最多有
2^k-1
个结点
~
最多有
2^(k-1)
个结点
~
所以此题
~
最多有
2^5-1=31
个结点
~
最多有
2^(5-1)=16
个叶子结点
~
4.
某二叉树中度为
2
的结点有
18
个,则该二叉树中有几个叶子结点?
结点的度是指树中每个结点具有的子树个数或者说是后继结点数。
题中的度为
2
是说具有的
2
个子树的结点;
个子树的结点;
二叉树有个性质:二叉树上叶子结点数等于度为
2
的结点数加
1
。
5.
在深度为
7
的满二叉树中,度为
2
的结点个数为多少,
就是第一层只有一个节点,他有两个子节点,第二层有两个节点,他们也都有两个子节点
就是第一层只有一个节点,他有两个子节点,第二层有两个节点,他们也都有两个子节点
以此类推,所以到第
6
层,就有
2
的
5
次方个节点,他们都有两个子节点
次方个节点,他们都有两个子节点
最后第
7
层都没有子节点了。因为是深度为
7
的。
的。
所以就是
1+2+4+8+16+32
了
2
深度为
1
的时候有
0
个
深度为
2
的时候有
1
个
深度为
3
的时候有
3
个
深度为
4
的时候有
7
个
....
深度为
n
的时候有(
2
的
n-1
次方减
1
)个
)个
6.
一棵二叉树中共有
70
个叶子结点与
80
个度为
1
的结点,则该二叉树中的总结点
数为?
假设
n
表示二叉树的所有结点数,
n0
表示度为
0
的结点
(
叶子结点
)
,
n1
表示度
为
1
的结点,
n2
表示度为
2
的结点,由二叉树的性质有:
的结点,由二叉树的性质有:
n0 = n2 + 1
已知
n0 = 70
,
则
n2 = n0 -1 = 69
而
n = n0 + n1 + n2
= 70 + 80 + 69
= 219
总结点数 n=70+80+70-1=219
总结点数
n=70+80+70-1=219
2解:对任一二叉树
解:对任一
二叉树,如果其叶子结点
,如果其
叶子结点为n0,度为
n0
,度为1的结点数为n1,度为
n1,
度为2的结
点数为n2,则
n2
,则n0=n2+1;
然后由
然后由n=n0+n1+n2①即可得出。(n
n=n0+n1+n2①即可得出。
(n为结点总数)
为结点总数
)
证明上一结论:由二叉树的特点可知,除了
证明上一结论:由二叉树的特点可知,除了根结点外,所有的结点都是由一
个分支引出来的,因此分支数为A=n-1,而二叉树中的分支都是由度为
A=n-1,
而二叉树中的分支都是由度为1和度为2
的结点发出的,因此有A=n1+2*n2,于是
A=n1+2*n2,
于是A=n-1=n1+2*n2,得到:n=n1+2*n2+1②
A=n-1=n1+2*n2,
得到:n=n1+2*n2+1②
得到:n=n1+2*n2+1②
由①与②可得:
由①与②可得:n0=n2+1
由①与②可得:
n0=n2+1
则该二叉树共有几个结点
7.
某二叉树有
5
个度为
2
的结点和
3
个度为
1
的结点,
二叉树性质:终端结点(叶子节点)个数
n0
=
度为
2
的节点(有
2
个孩子)
个数
n2 + 1
即
n0 = n2 + 1
。
所以本题有:叶子节点个数 ,
所以本题有:叶子节点个数
= 5 + 1 = 6
度为
1
的结点个数 ,
的结点个数
= 3
度为
2
的结点个数 ,
的结点个数
= 5
所以总个数
所以总个数 = 6 + 3 + 5 = 14
所以总个数
= 6 + 3 + 5 = 14
2对任何一棵二叉树
T
,如果其终端结点数为
n0
,度为
2
的结点数为
n2
,则
n0
= n2 + 1
故叶子结点数(即度为
0
的结点)为
5+1=6
二叉树的结点数为
n=n0+n1+n2
所以该二叉树的结点为:
5+3+6=14
|