第六章 树

第六章 树

一、选择题

1．对于一棵具有n个结点的树，该树中所有结点的度数之和为________。 A． n-1 B. n C. n+1 D. (n+1)/2

2．设结点A 有3个兄弟结点且结点B为结点A的双亲结点，则结点B 的度数为________。

A． 3 B. 4 C.5 D. 1 3．根据二叉树的定义可知二叉树共有________种不同的形态。 A． 4 B. 5 C. 6 D. 7 4．在一棵树中，________没有前驱结点。

A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点

5．设某棵二叉树中只有度数为0和度数为2的结点,且度数为0的结点数为 n，则这棵二叉中共有________个结点。

A． 2n B.n+1 C. 2n-1 D.2n+1

6．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有________。 A． 20 B.256 C. 512 D.1024 7. 一棵具有5层满二叉树中结点总数为________。 A． 31 B. 32 C.33 D.16 8. 如下图所示的4 棵二叉树，_______不是完全二叉树。

9.具有65个结点的完全二叉树的高度为________。 (根的层次号为1)

A.8 B.7 C.6 D.5

10.把一棵深度4的左单支二叉树改造成完全二叉树时，要增添 个空结点。

A．10

B．8

C．6

D．4

11.设按照从上到下、从左到右的顺序从 1 开始对完全二叉树进行顺序编号，则编号为 i结点的左孩子结点的编号为________。

A． 2i+1 B. 2i C. i/2 D. 2i-1

12.首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为________。

A.前序遍历 B.后序遍历 C.中序遍历 D.层次遍历 13.已知一棵二叉树的前序遍历结果为 ABCDEF ，中序遍历结果为 CBAEDF，则后序遍历的结果为________。

A．CBEFDA B. FEDCBA C. CBEDFA D. 不定

14.已知某二叉树的后序遍历序列是 dabec, 中序遍历序列是 debac,它的前序遍历序列是________。

A．acbed B．decab C．deabc D．cedba 15.某二叉树T有n个结点，设按某种遍历顺序对T中的每个结点进行编号，编号值为1,2,…,n且有如下性质：T中任一结点V，其编号等于左子树上的最小编号减1，而V的右子树 的结点中，其最小编号等于V左子树上结点的最大编号加1。这时按 编号。

A.中序遍历序列 B.前序遍历序列 C.后序遍历序列 D.层次遍历序列 16.某非空二叉树的前序序列和后序序列正好相反，则二叉树一定是________的二叉树。

A.空或只有一个结点 B.高度等于其结点数 C.任一结点无左孩子 D.任一结点无右孩子 17.由前序序列和中序序列________唯一确定一棵二叉树。 A． 能 B. 不能 C. 不一定

18.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。这里，我们把由树转化得到的二叉树叫做这棵树对应的二叉树。下面结论正确的是________。

A．树的先根遍历序列与其对应的二叉树的先序遍历序列相同 B．树的后根遍历序列与其对应的二叉树的后序遍历序列相同 C. 树的先根遍历序列与其对应的二叉树的中序遍历序列相同 D．以上都不对

19.对于一棵具有n个结点的二叉树，对应二叉链表中指针总数为 2n 个，其中________ 个用于指向孩子结点。

A． n-1 B. n C. n+1 D.n-2

20.设F是由T1、T2和T3 三棵树组成的森林，与F对应的二叉树为B，T1、T2 和T3 的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为________。

A． N1-1 B. N2-1 C. N2+N3 D. N1+N3

21. 由分别带权为9、2、5、7的四个叶子结点构造一棵哈夫曼树，该树的带权路径长度为 __ ___。

A. 23 B. 37 C. 44 D.46 22.n 个权构成一棵Huffman树，其结点总数为__________。

A．2n-1 B.2n C.2n+1 D. 不确定

二、填空题

1. 在一棵二叉树中，度为0的结点的个数为n0 ，度为2的结点的个数为n2 ，则：n0 = 。

2．结点数为7的二叉树的高度最矮是_______ ，最高是_______ 。 3．给定二叉树的结点数，要使树高为最大，那么该树应该是_______形状。 4．给定二叉树的结点数，要使树高为最矮，那么该树应该是_______形状。 5．如果一棵满二叉树的深度为7，那么它共有_______个结点，有 _______个叶结点。

6．深度为5的二叉树，至多有_______个结点。

7．深度为k 的完全二叉树至少有_______个结点，至多有_______个结点。 8．在树形结构中，树根结点没有前驱结点，其余每个结点有且只有_______ 个前驱结点，叶子结点没有后继结点，其余每个结点的后继结点可以有_______个。 9.设二叉树中度数为0 的结点数为50，度数为1 的结点数为30，则该二叉树中总共有_______个结点。

10.设二叉树中结点的两个指针域分别为lchild 和rchild，则判断指针变量p 所指向的结点为叶子结点的条件是___________________________。

11. 在n 个带权叶子结点构造出的所有二叉树中，带权路径长度最小的二叉树称为________。

12.设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1 开始顺序编号，则编号为8 的双亲结点的编号是_____，编号为8 的左孩子结点的编号是_______。

13. 设哈夫曼树中共有n 个结点，则该哈夫曼树中有_____个度数为1 的结点。 14. 以数据集{4，5，6，7，10，12，18}为结点权值所构造的Huffman 树为____，其带权路径长度为_________ 。

15.设一棵Huffman 树有6 个叶结点，权值分别为3、4、7、14、15、20，则根 结点的权值是_______。

16.设用于通信的电文仅由8 个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为_________。

三、综合应用题

1. 已知一棵树的边的集合表示为{（L,N）,（G,K）,（G,L）,（G,M）,（B,E）,（B,F）,（D,G）,（D,H）,（D,I）,（D,J）,（A,B）,（A,C）,（A,D）}。画出这棵树并回答下面问题：

（1） 树的根节点是哪个，哪些是叶子结点，哪些是非终端结点。 （2） 树的深度是多少，各个结点的层数是多少。

（3） 对于G结点，它的双亲结点、祖先结点、孩子结点、子孙结点、兄弟和堂兄弟分别是哪些结点。

2.设二叉树如下图所示，分别写出它的先序遍历、中序遍历、后序遍历序列。

J D H I B C A E F G 3.设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应

的二叉树，并写出对应后序遍历序列。

4.某二叉树结点的中序序列为HBCDEFG，后序序列为BDCHFGE，请据此画出该二叉树，再给该树加上中序线索。

5.请按照孩子-兄弟表示法，将下图所示树转化为二叉树。

G E F B C D A 6.若7个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶结点构造一棵哈夫曼树（请按照每个结点的左子树根结点的权小于等于右子树根结点的权的次序构造），计算出带权路径长度WPL及该树的结点总数。

7.在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题： （1）什么是哈夫曼树？

（2）根据题目所给频率值，画出相应的哈夫曼树。 （3）给出各个字符对应的哈夫曼编码。 （4）该段文字经过哈夫曼编码后，长度是多少。

四、算法设计题

1. 设计一个求结点x在二叉树中的双亲结点的算法。 2. 设计判断两个二叉树是否相同的算法。 3. 设计计算二叉树中所有结点值之和的算法。 4. 设计求二叉树中值为x的结点所在的层号的算法。

本文来源：https://www.bwwdw.com/article/2hyp.html