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

本文格式为Word版，下载可任意编辑——第5章树与二叉树习题参考答案

习题五参考答案

一、选择题

1．对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行（B）遍历操作一致。

A．先根B.中根C.后根D.层次

2．在哈夫曼树中，任何一个结点它的度都是（C）。

B．0或1B.1或2C.0或2D.0或1或2

3．对一棵深度为h的二叉树，其结点的个数最多为（D）。

h-1hA．2hB.2h-1C.2D.2-1

4．一棵非空二叉树的先根遍历与中根遍历正好一致，则该二叉树满足（A）

A．所有结点无左孩子B.所有结点无右孩子

C.只有一个根结点D.任意一棵二叉树

5．一棵非空二叉树的先根遍历与中根遍历正好相反，则该二叉树满足（B）

B．所有结点无左孩子B.所有结点无右孩子

C.只有一个根结点D.任意一棵二叉树

6．假设一棵二叉树中度为1的结点个数为5，度为2的结点个数为3，则这棵二叉树的叶结点的个数是（C）

A．2B.3C.4D.5

7．若某棵二叉树的先根遍历序列为ABCDEF，中根遍历序列为CBDAEF，则这棵二叉树的后根遍历序列为（B）。

A．FEDCBAB.CDBFEAC.CDBEFAD.DCBEFA

8．若某棵二叉树的后根遍历序列为DBEFCA，中根遍历序列为DBAECF，则这棵二叉树的先根遍历序列为（B）。

A．ABCDEFB.ABDCEFC.ABCDFED.ABDECF

9．根据以权值为{2，5，7，9，12}构造的哈夫曼树所构造的哈夫曼编码中最大的长度为（B）

A．2B.3C.4D.5

10．在有n个结点的二叉树的二叉链表存储结构中有（C）个空的指针域。

A．n-1B.nC.n+1D.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个结点，至多有2-1个结点。

8.对一棵树转换成的二叉树进行先根遍历所得的遍历序列为ABCDEFGH,则对这棵树进行

先根遍历所得的遍历序列为ABCDEFGH。

9.二叉树常用的存储结构是二叉链式存储结构，树常用的存储结构是孩子兄弟链表存

储结构。

10.对森林进行后根遍历操作等同于从左到右对森林中的每一棵树进行后根遍历操作，并

且对森林的后根遍历序列与对森林所对应的二叉树的中根遍历序列一致。

四、算法设计题

1.编写一个基于二叉树类的统计叶结点数目的成员函数。

参考答案：

publicintcountLeafNode(BiTreeNodeT){//统计叶结点数目intcount=0;if(T!=null){if(T.getLchild()==nullT.getRchild()==null){++count;//叶结点数增1}else{count+=countLeafNode(T.getLchild());//加上左子树上叶结点数count+=countLeafNode(T.getRchild());//加上右子树上的叶结点数}}returncount;}k2.编写一个基于二叉树类的查找二叉树结点的成员函数。

参考答案：

publicBiTreeNodesearchNode(BiTreeNodeT,Objectx){

//在以T为根结点的二叉树中查找值为x的结点,若找到,则返回该结点,否则返回空值if(T!=null){

if(T.getData().equals(x))

returnT;

else{

BiTreeNodelresult=searchNode(T.getLchild(),x);//在左子树上查找return(lresult!=null?lresult:searchNode(T.getRchild(),x));

//若左子树上没找到,则到右子树上找

}}returnnull;}

3.编写算法求一棵二叉树的根结点root到一个指定结点p之间的路径并输出。

参考答案：

//求根结点到指定结点的路径过程中，采用了后跟遍历的思想，最终求得的路径保存在一个链栈中，其中根结点处于栈顶位置，指定结点处于栈底位置。

//下面用到的二叉树结点类BiTreeNode在书中第5章中已给出

publicLinkStackgetPath(BiTreeNoderoot,BiTreeNodep){

BiTreeNodeT=root;

LinkStackS=newLinkStack();//构造链栈

if(T!=null){

S.push(T);//根结点进栈

Booleanflag;//访问标记

BiTreeNodeq=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进行倒置，以保证根结点处于栈顶位置LinkStackS2=newLinkStack();

while(!S.isEmpty())

S2.push(S.pop());

returnS2;

}

S.pop();//移除栈顶元素

q=T;//q指向刚被访问的结点

flag=true;//设置访问标记

}else{

S.push(T.getRchild());//右孩子结点入栈

flag=false;//设置未被访问标记

}

if(!flag)

break;

}

}

}

returnnull;

}

4.编写算法统计树(基于孩子兄弟链表存储结构)的叶子数目。

参考答案：

//下面用到的孩子兄弟链表结构中的结点类CSTreeNode在书中第5章中已给出publicintcountLeafNode(CSTreeNodeT){

intcount=0;

if(T!=null){

if(T.getFirstchild()==null)

++count;//叶结点数增1

else

count+=countLeafNode(T.getFirstchild());//加上孩子上叶结点数count+=countLeafNode(T.getNextsibling());//加上兄弟上叶结点数}

returncount;

}

5.编写算法计算树(基于孩子兄弟链表存储结构)的深度。

参考答案：