数据机构第五章——java语言描述第5章树与二叉树习题参考答案.doc

(完整word版)数据机构第五章——java语言描述第5章树与二叉树习题参考答案

习题五参考答案
备注: 红色字体标明的是与书本内容有改动的内容

一、选择题
1．对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（ B ）遍历操作相同。
A． 先根 B. 中根 C. 后根 D. 层次
2．在哈夫曼树中，任何一个结点它的度都是（ C ）。
B． 0或1 B. 1或2 C. 0或2 D. 0或1或2
3．对一棵深度为h的二叉树，其结点的个数最多为（ D ）。
A． 2h B. 2h-1 C. 2h-1 D. 2h-1
4．一棵非空二叉树的先根遍历与中根遍历正好相同，则该二叉树满足（ A ）
A． 所有结点无左孩子 B. 所有结点无右孩子
C. 只有一个根结点 D. 任意一棵二叉树
5．一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（ B ）
B． 所有结点无左孩子 B. 所有结点无右孩子
C. 只有一个根结点 D. 任意一棵二叉树
6．假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（ C ）
A．2 B. 3 C. 4 D. 5
7．若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（ B ）。
A．FEDCBA B. CDBFEA C. CDBEFA D. DCBEFA
8．若某棵二叉树的后根遍历序列为DBEFCA，中根遍历序列为DBAECF，则这棵二叉树的先根遍历序列为（ B ）。
A．ABCDEF B. ABDCEF C. ABCDFE D. ABDECF
9．根据以权值为{2，5，7，9，12}构造的哈夫曼树所构造的哈夫曼编码中最大的长度为（ B ）
A．2 B. 3 C. 4 D. 5
10．在有n个结点的二叉树的二叉链表存储结构中有（ C ）个空的指针域。
A．n-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;// 叶结点数增1
else
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+1>h2?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,否则返回false
if (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两棵二叉树相等！");
else
System.out.println("T1、T2两棵二叉树不相等！");
if (e.isEqual(T1, T3))
System.out.println("T1、T3两棵二叉树相等！");
else
System.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 HuffmanNode[m];
int i;
for (i = 0; i < n; i++)
HN[i] = new HuffmanNode(W[i]);// 构造n个具有权值的结点
for (i = n; i < m; i++) {// 建赫夫曼树
// 在HN[0..i - 1]选择不在赫夫曼树中且weight最小的两个结点min1和min2
HuffmanNode min1 = selectMin(HN, i - 1);
min1.setFlag(1);
HuffmanNode min2 = selectMin(HN, i - 1);
min2.setFlag(1);

// 构造min1和min2的父结点，并修改且父结点的权值
HN[i] = new HuffmanNode();
min1.setParent(HN[i]);
min2.setParent(HN[i]);
HN[i].setLchild(min1);
HN[i].setRchild(min2);
HN[i].setWeight(min1.getWeight() + min2.getWeight());
}

// 从叶子到根逆向求每个字符的赫夫曼编码
int[][] HuffCode = new int[n][n];// 分配n个字符编码存储空间
for (int j = 0; j < n; j++) {
int start = n - 1;// 编码的开始位置，初始化为数组的结尾
for (HuffmanNode c = HN[j], p = c.getParent(); p != null; c = p,
p = p.getParent())
// 从叶子到根逆向求编码
if (p.getLchild().equals(c))// 左孩子编码为0
HuffCode[j][start--] = 0;
else
// 右孩子编码为1
HuffCode[j][start--] = 1;
HuffCode[j][start] = -1;// 编码的开始标志为 -1，编码是-1之后的0、1序列
}
return HuffCode;
}

// 在HN[0..i - 1]选择不在赫夫曼树中且weight最小的结点
private HuffmanNode selectMin(HuffmanNode[] HN, int end) {
HuffmanNode min = HN[end];
for (int i = 0; i <= end; i++) {
HuffmanNode h = HN[i];
if (h.getFlag() == 0 && h.getWeight() < min.getWeight())
// 不在赫夫曼树中且weight最小的结点
min = h;
}
return min;
}
}
//测试类
public class Exercise5_4_3 {
public static void main(String[] args) {
int[] W = { 23, 11, 5, 3, 29, 14, 7, 8 };// 初始化权值
HuffmanTree T = new HuffmanTree();// 构造赫夫曼树
int[][] HN = T.huffmanCoding(W);// 求赫夫曼编码

System.out.println("赫夫曼编码为：");
for (int i = 0; i < HN.length; i++) {// 输出赫夫曼编码
System.out.print(W[i] + " ");
for (int j = 0; j < HN[i].length; j++) {
if (HN[i][j] == -1) {// 开始标志符读到数组结尾
for (int k = j + 1; k < HN[i].length; k++)
System.out.print(HN[i][k]);// 输出
break;
}
}
System.out.println();// 输出换行
}
}
}
运行结果：