数据结构之二叉树习题练习

习题练习

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）
A 不存在这样的二叉树
B 200
C 198
D 199

解答：

二叉树性质：==n0 = n2 + 1==

目前：n2 = 199 所以n0 = 200

叶子结点->度为0-> n0 = 200

所以答案为：B

2.下列数据结构中，不适合采用顺序存储结构的是（ ）
A 非完全二叉树  
B 堆
C 队列
D 栈

选择A

3.在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）
A n ->
B n+1
C n-1
D n/2

二叉树性质：n0 = n2 + 1

完全二叉树特点：==X1 -> [0，1]，最多只有一个度为1的结点==

解题思路：

4.一棵完全二叉树的节点数位为531个，那么这棵树的高度为（ ）
A 11
B 10
C 8
D 12

满二叉树是完全二叉树的特殊情况

==完全二叉树结点范围：[2^(h-1),2^h -1 ]== 所以高度范围为：[logN +1 , log（N+1)]

2^(h -1) = N ==> h= logN +1 2^h -1 = N ==> h = log (N+1) (log 以2为底的

==完全二叉树高度范围：[ logN +1 , log (N+1) ]==

h = 10 ： [512,1023] 531刚好在范围内 ->B

5.一个具有767个节点的完全二叉树，其叶子节点个数为（）
A 383
B 384
C 385
D 386

完全二叉树度为1的结点最多只有一个

1个

0个