【数据结构】二叉树经典例题—＜你真的掌握二叉树了吗?＞(第二弹)

本次选题都为选择题。涉及到二叉树总结点和叶子结点的计算、二叉树的基本性质、根据二叉树的前序/后序和中序遍历画出二叉树、哈夫曼树等等…希望对你有帮助哦~😝

1.若一颗二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为()
A.9 B.11 C.15 D.不确定

分析：本题为求解二叉树的度为0的结点个数，也就是求叶子结点。在做此类题时，我们一般设两个未知数，即总结点n，和叶结点。计算方法即，从两个角度看二叉树，从而列出等式。
二叉树的总结点树等于各不同性质结点之和即,从而，。二叉树的终结点数等于
结点的度*该性质结点的个数+1，(这个加的1即为这个树的根节点)即,从而可以解得.
故此题选B。

2.一颗完全二叉树上有1001个结点，其中叶子结点的个数为()
A.250 B.500 C.502 D.以上均不对

分析：本题涉及到了满二叉树的总结点数和层结点数的基本知识。

3.具有10个叶子结点的完全二叉树中有()个度为2的结点。
A.8 B.9 C.10.D11

分析：根据二叉树的性质，对任何一棵二叉树T，如果其终端结点数为，度为2的结点数为，则
对于这个性质呢，我是根据二叉树的两种结点的计算方法联立，消去，从而得到和的关系式。

4.设给定权值结点总数有n个，那么哈夫曼树的结点总数为()。
A.不确定 B.2n C.2n+1 D.2n-1

分析：
这个题需要理解哈夫曼树的构造，哈夫曼树即是将森林中的树不断地合二为一，最终形成最优二叉树。我是根据基本的规律得出结论，给定权值结点的总数为2，那么哈夫曼树结点为3；给定权值结点的总数为3，那么哈夫曼树的结点为5…那么给定权值结点的总数为n，则哈夫曼树的结点总数为2n-1。
故本题选D。

5.用一组权值{3,6,8,10,11}构造一颗哈夫曼树，它的带权路径长度为()。
A.92 B.35 C.38 D.85

分析：本题的考察内容为哈夫曼树的构造以及基本的概念。
哈夫曼树构造的算法思想：
已知一组叶子结点的权值为则构造哈夫曼树的构成如下
①首先把n个叶子结点看作n棵树(仅有一个结点的二叉树),n棵树构成一颗森林。
②在森林中把权值最小和次小的两棵树合并成一棵树，该树结点的权值是两棵树根结点的权值之和，这时森林中就会减少一棵树。
③重复第②步直到森林中只有一颗二叉树为止。
对于本题，设权值{3,6,8,10,11}对应的结点分别是a、b、c、d、e。
首先，这5棵树构成森林：

6.下列有关二叉树的说法中，正确的是()
A.二叉树的度为2
B.一颗二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2

分析：二叉树中的任何结点的度都小于等于2，可以为0，1，2。
故此题选B

7.二叉树的第i层上最多含有结点数为()
A. B.-1 C. D.-1

分析：二叉树的基本性质，第i层上最多含有个结点。
故本题选C。

8.一颗具有n个结点的完全二叉树的深度为()
A. B. C.[] D.

分析：二叉树的基本性质，一颗具有n个结点的完全二叉树的深度为
故本题选A。

9.在一棵深度为k的满二叉树中，结点总数为()
A. B. C. D.[]+1

分析：二叉树的基本性质，在一棵深度为k的满二叉树中，结点总数为
故此题选C。

10.一颗二叉树的先序遍历序列为ABCDEFG，它的中序遍历序列可能是（） A.CABDEFG B.ABCDEFG C.DACEFBG D.ADCEFG

分析：这个题，可以从很多方面进行排除。
首先，我们可以很确定的是这棵树的根节点为A。
我比较喜欢采用中序遍历的特点，将这棵树可能的形状进行想象，从而排除。
中序遍历的特点就是，将一颗树压扁之后，即压制同一水平线，就是中序遍历的结果。

11.已知某二叉树的后序遍历序列为DABEC，中序遍历序列为DEBAC，它的先序遍历序列是()。
A.ACBED B.DECAB C.DEABC D.CEDBA

分析：此类题目是经典根据中序遍历和先序/后序遍历得出后序/先序遍历的题。此类题需要我们根据已知的信息发出这颗二叉树，从而得出它的先序/后序遍历。
做这类题都是根据先序、中序、后序遍历的特点分析：先序顺序即：根->左子树->右子树，中序遍历为：左子树->根->右子树，后序遍历为:左子树->右子树->根。
对于本题，根据后序遍历，得出根节点C。