第5章 树与二叉树习题参考答案.doc

1、习题五参考答案备注: 红色字体标明的是与书本内容有改动的内容 一、选择题1对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（ B ）遍历操作相同。A 先根 B. 中根 C. 后根 D. 层次2在哈夫曼树中，任何一个结点它的度都是（ C ） 。B 0 或 1 B. 1 或 2 C. 0 或 2 D. 0 或 1 或 23对一棵深度为 h 的二叉树，其结点的个数最多为（ D ） 。A 2h B. 2h-1 C. 2h-1 D. 2h-14一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足（ A ）A 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树5

2、一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（ B ）B 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树6假设一棵二叉树中度为 1 的结点个数为 5，度为 2 的结点个数为 3，则这棵二叉树的叶结点的个数是（ C ）A2 B. 3 C. 4 D. 57若某棵二叉树的先根遍历序列为 ABCDEF，中根遍历序列为 CBDAEF，则这棵二叉树的后根遍历序列为（ B ） 。AFEDCBA B. CDBFEA C. CDBEFA D. DCBEFA8若某棵二叉树的后根遍历序列为 DBEFCA，中根遍历序列为 DBAECF，则这棵二叉树的先根遍历序列为（

3、 B ） 。AABCDEF B. ABDCEF C. ABCDFE D. ABDECF9根据以权值为2，5，7，9，12构造的哈夫曼树所构造的哈夫曼编码中最大的长度为（ B ）A2 B. 3 C. 4 D. 510在有 n 个结点的二叉树的二叉链表存储结构中有（ C ）个空的指针域。An-1 B. n C. n+1 D. 0二、填空题1. 在一棵度为 m 的树中，若度为 1 的结点有 n1 个，度为 2 的结点有 n2 个，度为m 的结点有 nm 个，则这棵树中的叶结点的个数为 1+n 2+2n3+3n4+(m-1)nm 。2. 一棵具有 n 个结点的二叉树，其深度最多为 n ，最少为 log

4、 2n+1 。3. 一棵具有 100 个结点的完全二叉树，其叶结点的个数为 50 。4. 以5，9，12，13，20，30为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。5. 有 m 个叶结点的哈夫曼树中，结点的总数是 2m-1 。6. 若一棵完全二叉树的第 4 层(根结点在第 0 层)有 7 个结点，则这棵完全二叉树的结点总数是 11 。7. 在深度为 k 的完全二叉树中至少有 k 个结点，至多有 2 k-1 个结点。8. 对一棵树转换成的二叉树进行先根遍历所得的遍历序列为 ABCDEFGH,则对这棵树进行先根遍历所得的遍历序列为 ABCDEFGH 。9. 二叉树常用的存储结构是

5、二叉链式存储结构 ，树常用的存储结构是 孩子兄弟链表存储结构 。10. 对森林进行后根遍历操作等同于从左到右对森林中的每一棵树进行 后根 遍历操作，并且对森林的后根遍历序列与对森林所对应的二叉树的 中根 遍历序列相同。四、算法设计题1. 编写一个基于二叉树类的统计叶结点数目的成员函数。参考答案：public int countLeafNode(BiTreeNode T) / 统计叶结点数目int count = 0;if (T != null) if (T.getLchild() = null / 叶结点数增 1 else count += countLeafNode(T.getLchild(

6、); / 加上左子树上叶结点数count += countLeafNode(T.getRchild();/ 加上右子树上的叶结点数return count;2. 编写一个基于二叉树类的查找二叉树结点的成员函数。参考答案：public BiTreeNode searchNode(BiTreeNode T,Object x) / 在以 T 为根结点的二叉树中查找值为 x 的结点,若找到,则返回该结点,否则返回空值if (T != null) if (T.getData().equals(x)return T;else BiTreeNode lresult= searchNode(T.getLchi

7、ld(),x); / 在左子树上查找return (lresult!=null?lresult:searchNode(T.getRchild(),x) ;/ 若左子树上没找到,则到右子树上找return null;3. 编写算法求一棵二叉树的根结点 root 到一个指定结点 p 之间的路径并输出。参考答案：/ 求根结点到指定结点的路径过程中，采用了后跟遍历的思想，最终求得的路径保存在一个链栈中，其中根结点处于栈顶位置，指定结点处于栈底位置。/下面用到的二叉树结点类 BiTreeNode 在书中第 5 章中已给出public LinkStack getPath(BiTreeNode root,

8、BiTreeNode p) BiTreeNode T = root;LinkStack S = new LinkStack();/ 构造链栈if (T != null) S.push(T); / 根结点进栈Boolean flag;/ 访问标记BiTreeNode q = null;/ q 指向刚被访问的结点while (!S.isEmpty() while (S.peek() != null)/ 将栈顶结点的所有左孩子结点入栈S.push(BiTreeNode) S.peek().getLchild();S.pop(); / 空结点退栈while (!S.isEmpty() T = (BiT

9、reeNode) S.peek();/ 查看栈顶元素if (T.getRchild() = null | T.getRchild() = q) if (T.equals(p) / 对栈 S 进行倒置，以保证根结点处于栈顶位置LinkStack S2 = new LinkStack();while (!S.isEmpty()S2.push(S.pop();return S2;S.pop();/ 移除栈顶元素q = T;/ q 指向刚被访问的结点flag = true;/ 设置访问标记 else S.push(T.getRchild();/ 右孩子结点入栈flag = false;/ 设置未被访问

10、标记if (!flag)break;return null;4. 编写算法统计树(基于孩子兄弟链表存储结构)的叶子数目。参考答案：/下面用到的孩子兄弟链表结构中的结点类 CSTreeNode 在书中第 5 章中已给出public int countLeafNode(CSTreeNode T) int count = 0;if (T != null) if (T.getFirstchild() = null)+count;/ 叶结点数增 1elsecount += countLeafNode(T.getFirstchild(); / 加上孩子上叶结点数count += countLeafNode

11、(T.getNextsibling();/ 加上兄弟上叶结点数return count;5. 编写算法计算树(基于孩子兄弟链表存储结构)的深度。参考答案：public int treeDepth(CSTreeNode T) if (T != null) int h1= treeDepth(T.getFirstchild();int h2= treeDepth(T.getNextsibling();return h1+1h2?h1+1:h2;return 0;四、上机实践题1. 编写一个程序实现：先建立两棵以二叉链表存储结构表示的二叉树，然后判断这两棵二叉树是否相等并输出测试结果。参考答案：pa

12、ckage ch05Exercise;import ch05.BiTreeNode;/教材第 5 章中有此类的描述public class Exercise5_4_1 public boolean isEqual(BiTreeNode T1, BiTreeNode T2) /判断两棵树是否相等，若相等则返回 true,否则返回 falseif (T1 = null if (T1 != null return false;/测试主方法public static void main(String args) / 创建根结点为 T1 的二叉树BiTreeNode D1 = new BiTreeNod

13、e(D);BiTreeNode G1 = new BiTreeNode(G);BiTreeNode H1 = new BiTreeNode(H);BiTreeNode E1 = new BiTreeNode(E, G1, null);BiTreeNode B1 = new BiTreeNode(B, D1, E1);BiTreeNode F1 = new BiTreeNode(F, null, H1);BiTreeNode C1 = new BiTreeNode(C, F1, null);BiTreeNode T1 = new BiTreeNode(A, B1, C1);/ 创建根结点为 T2

14、 的二叉树BiTreeNode D2 = new BiTreeNode(D);BiTreeNode G2 = new BiTreeNode(G);BiTreeNode H2= new BiTreeNode(H);BiTreeNode E2 = new BiTreeNode(E, G2, null);BiTreeNode B2 = new BiTreeNode(B, D2, E2);BiTreeNode F2 = new BiTreeNode(F, null, H2);BiTreeNode C2 = new BiTreeNode(C, F2, null);BiTreeNode T2 = new

15、BiTreeNode(A, B2, C2);/ 创建根结点为 T3 的二叉树BiTreeNode E3= new BiTreeNode(E);BiTreeNode F3 = new BiTreeNode(F);BiTreeNode D3= new BiTreeNode(D,F3,null);BiTreeNode B3 = new BiTreeNode(B, null, D3);BiTreeNode C3 = new BiTreeNode(C, null, E3);BiTreeNode T3 = new BiTreeNode(A, B3, C3);Exercise5_4_1 e = new Ex

16、ercise5_4_1();if (e.isEqual(T1, T2)System.out.println(“T1、T2 两棵二叉树相等！“);elseSystem.out.println(“T1、T2 两棵二叉树不相等！“);if (e.isEqual(T1, T3)System.out.println(“T1、T3 两棵二叉树相等！“);elseSystem.out.println(“T1、T3 两棵二叉树不相等！“);运行结果：2编写一个程序实现：先建立一棵以孩子兄弟链表存储结构表示的树，然后输出这棵树的先根遍历序列和后根遍历序列。参考答案：package ch05Exercise;im

17、port ch05.CSTreeNode; /教材第 5 章中有此类的描述public class Exercise5_4_2 /创建一棵树public CSTreeNode createBiTree() CSTreeNode D = new CSTreeNode(D);CSTreeNode E = new CSTreeNode(E);CSTreeNode C = new CSTreeNode(C, D, E);CSTreeNode B = new CSTreeNode(B, null, C);CSTreeNode A = new CSTreeNode(A, B, null);return A

18、;/ 先根遍历树的递归算法public void preRootTraverse(CSTreeNode T) if (T != null) System.out.print(T.getData(); / 访问根结点preRootTraverse(T.getFirstchild();/ 访问孩子结点preRootTraverse(T.getNextsibling();/ 访问兄弟结点/ 后根遍历树的递归算法public void postRootTraverse(CSTreeNode T) if (T != null) postRootTraverse(T.getFirstchild();/ 访

19、问孩子结点System.out.print(T.getData(); / 访问根结点postRootTraverse(T.getNextsibling();/ 访问兄弟结点public static void main(String args) Exercise5_4_2 e = new Exercise5_4_2();CSTreeNode root=e.createBiTree();/ 调试先根遍历System.out.println(“该树的先根遍历为：“);e.preRootTraverse(root);/ 调试后根遍历System.out.println(“n 该树的后根遍历为：“);

20、e.postRootTraverse(root);运行结果：3编写一个基于构造哈夫曼树和哈夫曼编码的 HuffmanCoding 类的测试程序，使其实现先建立一棵哈夫曼树，然后再根据这棵哈夫曼树来构造并输出其哈夫曼编码。参考答案：package ch05Exercise;import ch05.HuffmanNode; /教材第 5 章中有此类的描述/构造哈夫曼树和哈夫曼编码的 HuffmanCoding 类class HuffmanTree / 求赫夫曼编码的算法，W 存放 n 个字符的权值(均0)public int huffmanCoding(int W) int n = W.lengt

21、h;/ 字符个数int m = 2 * n - 1;/ 赫夫曼树的结点数HuffmanNode HN = new HuffmanNodem;int i;for (i = 0; i n; i+)HNi = new HuffmanNode(Wi);/ 构造 n 个具有权值的结点for (i = n; i m; i+) / 建赫夫曼树/ 在 HN0.i - 1选择不在赫夫曼树中且 weight 最小的两个结点 min1 和 min2HuffmanNode min1 = selectMin(HN, i - 1);min1.setFlag(1);HuffmanNode min2 = selectMin(

22、HN, i - 1);min2.setFlag(1);/ 构造 min1 和 min2 的父结点，并修改且父结点的权值HNi = new HuffmanNode();min1.setParent(HNi);min2.setParent(HNi);HNi.setLchild(min1);HNi.setRchild(min2);HNi.setWeight(min1.getWeight() + min2.getWeight();/ 从叶子到根逆向求每个字符的赫夫曼编码int HuffCode = new intnn;/ 分配 n 个字符编码存储空间for (int j = 0; j n; j+) i

23、nt start = n - 1;/ 编码的开始位置，初始化为数组的结尾for (HuffmanNode c = HNj, p = c.getParent(); p != null; c = p, p = p.getParent()/ 从叶子到根逆向求编码if (p.getLchild().equals(c)/ 左孩子编码为 0HuffCodejstart- = 0;else/ 右孩子编码为 1HuffCodejstart- = 1;HuffCodejstart = -1;/ 编码的开始标志为 -1，编码是-1 之后的 0、1 序列return HuffCode;/ 在 HN0.i - 1选择

24、不在赫夫曼树中且 weight 最小的结点private HuffmanNode selectMin(HuffmanNode HN, int end) HuffmanNode min = HNend;for (int i = 0; i = end; i+) HuffmanNode h = HNi;if (h.getFlag() = 0 return min;/测试类public class Exercise5_4_3 public static void main(String args) int W = 23, 11, 5, 3, 29, 14, 7, 8 ;/ 初始化权值HuffmanTr

25、ee T = new HuffmanTree();/ 构造赫夫曼树int HN = T.huffmanCoding(W);/ 求赫夫曼编码System.out.println(“赫夫曼编码为：“);for (int i = 0; i HN.length; i+) / 输出赫夫曼编码System.out.print(Wi + “ “);for (int j = 0; j HNi.length; j+) if (HNij = -1) / 开始标志符读到数组结尾for (int k = j + 1; k HNi.length; k+)System.out.print(HNik);/ 输出break;System.out.println();/ 输出换行运行结果：