第5章 树与二叉树习题参考答案
更新时间:2024-06-03 12:06:01 阅读量: 综合文库 文档下载
习题五参考答案
备注: 红色字体标明的是与书本内容有改动的内容
一、选择题
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. 2 D. 2-1
4.一棵非空二叉树的先根遍历与中根遍历正好相同,则该二叉树满足( A ) A. 所有结点无左孩子 B. 所有结点无右孩子 C. 只有一个根结点 D. 任意一棵二叉树
5. 一棵非空二叉树的先根遍历与中根遍历正好相反,则该二叉树满足( B )
A. 所有结点无左孩子 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 。 h-1
h
2. 一棵具有n个结点的二叉树,其深度最多为 n ,最少为 [log2n]+1 。 3. 一棵具有100个结点的完全二叉树,其叶结点的个数为 50 。37
4. 以{5,9,12,13,20,30}为叶结点的权值所构造的哈夫曼树的带权路径长度是 217 。 5. 有m个叶结点的哈夫曼树中,结点的总数是 2m-1 。
6. 若一棵完全二叉树的第4层(根结点在第0层)有7个结点,则这棵完全二叉树的结点总
数是 11 。22
7. 在深度为k的完全二叉树中至少有 k个结点,至多有 2-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());// 加上右子树上的叶结点数
k
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) {
//
Exercise5_4_1 e = new Exercise5_4_1();
if (e.isEqual(T1, T3)) }
}
运行结果:// 创建根结点为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);
if (e.isEqual(T1, T2)) System.out.println(\、T2两棵二叉树相等!\else
System.out.println(\、T2两棵二叉树不相等!\
System.out.println(\、T3两棵二叉树相等!\else System.out.println(\、T3两棵二叉树不相等!\
正在阅读:
第5章 树与二叉树习题参考答案06-03
2018-2019年仪征市古井中心小学一年级上册数学复习题无答案12-21
个性化讲义之眼睛与光学仪器(附录答案)03-28
一次惊险的体验作文1000字07-04
信息技术与课程整合05-28
新视野大学英语(第三版)视听说第一册全册答案(附词汇测试及答案)03-20
现代汉语语法思考和练习答案11-28
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 习题
- 答案
- 参考