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

习题五参考答案备注: 红色字体标明的是与书本内容有改动的内容 一、选择题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一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（ 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，则这棵二叉树的先根遍历序列为（ 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+n2+2n3+3n4+(m-1)nm 。2. 一棵具有n个结点的二叉树，其深度最多为 n ，最少为 log2n+1 。3. 一棵具有100个结点的完全二叉树，其叶结点的个数为 50 。4. 以5，9，12，13，20，30为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。5. 有m个叶结点的哈夫曼树中，结点的总数是 2m-1 。6. 若一棵完全二叉树的第4层(根结点在第0层)有7个结点，则这棵完全二叉树的结点总数是 11 。7. 在深度为k的完全二叉树中至少有 k个结点，至多有 2k-1 个结点。8. 对一棵树转换成的二叉树进行先根遍历所得的遍历序列为ABCDEFGH,则对这棵树进行先根遍历所得的遍历序列为 ABCDEFGH 。9. 二叉树常用的存储结构是 二叉链式存储结构 ，树常用的存储结构是 孩子兄弟链表存储结构 。10. 对森林进行后根遍历操作等同于从左到右对森林中的每一棵树进行 后根 遍历操作，并且对森林的后根遍历序列与对森林所对应的二叉树的 中根 遍历序列相同。四、算法设计题1. 编写一个基于二叉树类的统计叶结点数目的成员函数。参考答案：public int countLeafNode(BiTreeNode T) / 统计叶结点数目int count = 0;if (T != null) if (T.getLchild() = null & T.getRchild() = null) +count;/ 叶结点数增1 else count += countLeafNode(T.getLchild(); / 加上左子树上叶结点数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.getLchild(),x); / 在左子树上查找return (lresult!=null?lresult:searchNode(T.getRchild(),x) ;/ 若左子树上没找到,则到右子树上找 return null;3. 编写算法求一棵二叉树的根结点root到一个指定结点p之间的路径并输出。参考答案：/ 求根结点到指定结点的路径过程中，采用了后跟遍历的思想，最终求得的路径保存在一个链栈中，其中根结点处于栈顶位置，指定结点处于栈底位置。/下面用到的二叉树结点类BiTreeNode在书中第5章中已给出public LinkStack getPath(BiTreeNode root, 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 = (BiTreeNode) 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;/ 设置未被访问标记if (!flag)break;return null;4. 编写算法统计树(基于孩子兄弟链表存储结构)的叶子数目。参考答案：/下面用到的孩子兄弟链表结构中的结点类CSTreeNode在书中第5章中已给出public int countLeafNode(CSTreeNode T) int count = 0;if (T != null) if (T.getFirstchild() = null) +count;/ 叶结点数增1else count += countLeafNode(T.getFirstchild(); / 加上孩子上叶结点数 count += countLeafNode(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. 编写一个程序实现：先建立两棵以二叉链表存储结构表示的二叉树，然后判断这两棵二叉树是否相等并输出测试结果。参考答案：package ch05Exercise;import ch05.BiTreeNode;/教材第5章中有此类的描述public class Exercise5_4_1 public boolean isEqual(BiTreeNode T1, BiTreeNode T2) /判断两棵树是否相等，若相等则返回true,否则返回falseif (T1 = null & T2 = null)/ 同时为空return true;if (T1 != null & T2 != null) / 同时非空进行比较if (T1.getData().equals(T2.getData()/ 根结点数据元素是否相等if (isEqual(T1.getLchild(), T2.getLchild() / 左子树是否相等 if (isEqual(T1.getRchild(), T2.getRchild()/ 右子树是否相等return true;return false; /测试主方法public static void main(String args) / 创建根结点为T1的二叉树BiTreeNode D1 = new BiTreeNode(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的二叉树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 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 Exercise5_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;import 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;/ 先根遍历树的递归算法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();/ 访问孩子结点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该树的后根遍历为：);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.length;/ 字符个数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(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+) int 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/ 右孩子编码为1HuffCodejsta