第六章 树习题及答案.docx
《第六章 树习题及答案.docx》由会员分享，可在线阅读，更多相关《第六章 树习题及答案.docx（43页珍藏版）》请在冰点文库上搜索。
第六章树习题及答案
第六章树习题及答案
一、基础知识题
6.1.假设在树中，结点x是结点y的双亲时,用（x,y）来表示树边.已知一棵树边的集合为{（i,m）,（i,n）,（e,i）,（b,e）,（b,d）,（a,b）,（g,j）,（g,k）,（c,g）,（c,f）,（h,l）,（c,h）,（a,c）}用树形表示法出此树，并回答下列问题：
（1）哪个是根结点?
（2）哪些是叶结点?
（3）哪个是g的双亲?
（4）哪些是g的祖先?
（5）哪些是g的孩子?
（6）哪些是e的子孙?
（7）哪些是e的兄弟?
哪些是f的兄弟?
（8）结点b和n的层次各是多少?
（9）树的深度是多少?
（10）以结点c为根的子树的深度是多少?
（11）树的度数是多少?
6.2一棵度为2的有序树与一棵二叉树有何区别?
6.3试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
6.4已知一棵度为m的树中有n1个度为1的结点，n2个度为2的结点，...nm个度为m的结点，问该树中有多少片叶子?
6.5一个深度为h的满k叉树有如下性质：
第h层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树。
如果按层次顺序（同层自左至右）从1开始对全部结点编号，问：
（1）各层的结点数目是多少?
（2）编号为i的结点的双亲结点（若存在）的编号是多少?
（3）编号为i的结点的第j个孩子结点（若存在）的编号是多少?
（4）编号为i的结点的有右兄弟的条件是什么?
其右兄弟的编号是多少?
6.6高度为h的完全二叉树至少有多少个结点?
至多有多少个结点?
6.7在具有n个结点的k叉树（k>=2）的k叉链表表示中，有多少个空指针?
6.8假设二叉树包含的结点数据为1，3，7，12。
（1）画出两棵高度最大的二叉树；
（2）画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。
6.9试找出分别满足下面条件的所有二叉树：
（1）前序序列和中序序列相同；
（2）中序序列和后序序列相同；
（3）前序序列和后序序列相同；（4）前序、中序、后序序列均相同。
6.10试采用顺序存储方法和链接存储方法分别画也6.30所示各二叉树的存储结构。
6.11分别写出图6.30（下图）所示各二叉树的前序、中序和后序序列。
6.12若二叉树中各结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一地确定一棵二叉树，但由前序序列和后序序列却不一定能唯一地确定一棵二叉树。
（1）已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画出此二叉树。
（1）已知一棵二叉树的在序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出此二叉树。
（1）已知一棵二叉树的前序序列和后序序列分别为AB和BA，请画出这两棵不同的二叉树。
6.13对二叉树中的结点进行按层次顺序（每一层自左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树层次序列。
现已知一棵二叉树的层次序列为ABCDEFGHIJ,中序序列为DBGEHJACIF，请画出此二叉树。
6.14试画出图6.30（下图）所示各二叉树的前序、中序和后序线索树及相应的线索链表。
6.15在何种线索树中，线索对求指定结点在相应次序下的前趋和后继并无帮助?
6.16对图6.31所示的森林：
（1）求各树的前序序列和后序序列；
（2）求森林的前序序列和后序序列；
（3）将此森林转换为相应的二叉树；
（4）给出（a）所示树的以亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄弟链表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代?
6.17画出图6.32（下图）所示的各二叉树所对就的森林。
6.18高度为h的严格二叉树至少有多少个结点?
至多有多少个结点?
6.19在什么样的情况下，等长编码是最优的前缀码?
6.20下述编码哪一组不是前缀码?
{00,01,10,11},{0,1,00,11},{0,10,110,111}
6.21假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.
（1）为这8个字母设计哈夫曼编码。
（2）若用这三位二进制数（0…7）对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?
它使电文总长平均压缩多少?
答案：
6.1:
图见网页动画。
答：
（这是测试我们对树的基本概念的掌握情况.）
a是根结点；
mndfjkl是叶结点；
c是g的双亲；
c,a是g的祖先；
j,k是g的孩子；
imn是e的子孙；
d是e的兄弟；g,h是f的兄弟；
b的层次是2；n的层次是5；
树的深度是5；
以c为根的子树深度是3；
树的度数是3；
6.2答：
一棵度为二的有序树与一棵二叉树的区别在于，有序树的结点次序是相对于另一结点而言的，如果有序树中的子树只有一个孩子时，这个孩子结点就无须区分其左右次序，而二叉树无论其孩子数是否为2，均需确定其左右次序，也就是说二叉树的结点次序不是相对于另一结点而言而是确定的。
6.3答：
三个结点的树如下：
只有两种形态
○A○A
/\|
○○○
|
○
三个结点的二叉树如下所示：
有五种形态：
（1）
（2）（3）（4）（5）
○A○A○A○A○A
/\//\\
○○○○○○
/\/\
○○○○
6.4解：
叶子数为：
n0=1+0*n1+1*n2+2*n3+...（m-1）*nm
评：
我们想象这棵树是从一个根开始长起来的：
当一棵树仅为根时，它的叶子数为1，每"长出"一个度为1的结点都不会增加叶子数，因此第二项为0，每长出一个度为2的结点时（无论是从哪一个结点长出）可以增加1片叶子，依此类推，每长出一个度为m的结点，可以增加（m-1）片叶子，把所有的叶子加起来就成了。
6.5解：
（1）设层号为l的结点数目为m=k^（l-1）
（2）编号为i的结点的双亲结点的编号是：
：
|_（i+k-2）/k_|（不大于（i+k-2）/k的最大整数。
也就是（i+k-2）与k整除的结果.以下/表示整除。
（3）编号为i的结点的第j个孩子结点编号是：
k*（i-1）+1+j;
（4）编号为i的结点有右兄弟的条件是（i+1）/k==（i+2）/k（整除）并且i!
=1
右兄弟的编号是i+1.
6.6解：
高度为h的完全二叉树至少有2^（h-1）个结点，至多有2^h-1个结点（也就是满二叉树）。
6.7解：
空指针的个数为：
n（k-1）+1;
6.8解：
（1）高度最大的两棵二叉树如图：
○1○1
/\
○3○3
/\
○7○7
/\
○2○2
/\
○12○12
（2）两棵完全二叉树如下：
○12○12
/\/\
○7○3○7○3
/\/\
○1○2○2○1
6.9答：
空树满足所有条件。
非空树如下：
（1）前序序列和中序序列相同的二叉树是：
没有左子树的二叉树（右单支树）。
（2）中序序列和后序序列相同的二叉树是：
没有右子树的二叉树（左单支树）。
（3）前序序列和后序序列相同的二叉树是：
只有根的二叉树。
（4）前序、中序、后序序列均相同的二叉树：
只有根结点的二叉树。
6.10
评：
此题测试我们对完全二叉树的掌握情况和两种存储方法的运用。
解：
顺序存储方法：
二叉树（a）:
下标0123456789101112131415161718192021
_____________________________________________________________
bt|5|1|2|∮|∮|3|∮|∮|∮|∮|4|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|5|
-------------------------------------------------------------
二叉树（b）:
下标01234567891011121314151617181920212223242526
__________________________________________________________________________________
bt|5|1|∮|2|∮|∮|3|∮|∮|∮|∮|∮|∮|4|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|5|
----------------------------------------------------------------------------------
二叉树（c）:
下标012345678910111213141516171819202122232425
_______________________________________________________________________________
bt|7|1|∮|2|∮|∮|3|4|∮|∮|∮|∮|5|6|∮|∮|∮|∮|∮|∮|∮|∮|∮|∮|7|8|
-------------------------------------------------------------------------------
二叉树（d）:
下标0123456789101112131415
___________________________________________________
bt|8|1|2|3|4|∮|5|6|∮|7|∮|∮|∮|∮|8|9|
--------------------------------------------------
链式存储结构：
----------------------------------------------------------------
二叉树（a）:
↓root
┌─┬─┬─┐
││1│∧│
└─┴─┴─┘
↓
┌─┬─┬─┐
│∧│2││
└─┴─┴─┘
↓
┌─┬─┬─┐
││3│∧│
└─┴─┴─┘
↓
┌─┬─┬─┐
│∧│4││
└─┴─┴─┘
↓
┌─┬─┬─┐
│∧│5│∧│
└─┴─┴─┘
---------------------------------------------------------------
二叉树（b）:
L
↓root
┌─┬─┬─┐
│∧│1││
└─┴─┴─┘
↓
┌─┬─┬─┐
││2│∧│
└─┴─┴─┘
↓
┌─┬─┬─┐
│∧│3││
└─┴─┴─┘
↓
┌─┬─┬─┐
││4│∧│
└─┴─┴─┘
↓
┌─┬─┬─┐
│∧│5│∧│
└─┴─┴─┘
二叉树（c）:
------------------------------------------------------------------------
↓root
┌─┬─┬─┐
│∧│1││
└─┴─┴─┘
↓
┌─┬─┬─┐
││2││
└─┴─┴─┘
↓↓
┌─┬─┬─┐┌─┬─┬─┐
││3│││∧│4│∧│
└─┴─┴─┘└─┴─┴─┘
↓↓
┌─┬─┬─┐┌─┬─┬─┐
││5│││∧│6│∧│
└─┴─┴─┘└─┴─┴─┘
↓↓
┌─┬─┬─┐┌─┬─┬─┐
│∧│7│∧││∧│8│∧│
└─┴─┴─┘└─┴─┴─┘
二叉树（d）:
-----------------------------------------------
↓root
┌─┬─┬─┐
││1││
└─┴─┴─┘
↓↓
┌─┬─┬─┐┌─┬─┬─┐
││2│∧│││3││
└─┴─┴─┘└─┴─┴─┘
↓↓↓
┌─┬─┬─┐┌─┬─┬─┐┌─┬─┬─┐
│∧│4│││∧│5│∧│││6││
└─┴─┴─┘└─┴─┴─┘└─┴─┴─┘
↓↓↓
┌─┬─┬─┐┌─┬─┬─┐┌─┬─┬─┐
│∧│7│∧││∧│8│∧││∧│9│∧│
└─┴─┴─┘└─┴─┴─┘└─┴─┴─┘
6.11解：
（a）前序序列：
12345中序序列：
24531后序序列：
54321
（b）前序序列：
12345中序序列：
13542后序序列：
54321
（c）前序序列：
12357864中序序列：
17583624后序序列：
78563421
（d）前序序列：
124735689中序序列：
472153869后序序列：
742589631
6.12解：
（1）已知二叉树的前序序列为ABDGHCEFI和中序序列GDHBAECIF，则可以根据前序序列找到根结点为A，由此，通过中序序列可知它的两棵子树包分别含有GDHB和ECIF结点，又由前序序列可知B和C分别为两棵子树的根结点...以此类推可画出所有结点：
○A
/\
○B○C
//\
○D○E○F
/\/
○G○H○I
（2）以同样的方法可画出该二叉树：
○A
/\
○B○F
\\
○C○G
/\/
D○E○○H
（3）这两棵不同的二叉树为：
○A○A
/\
○B○B
6.13解：
类似于上一题的分析方法，可画出二叉树的所有结点：
○A
/\
○B○C
/\\
○D○E○F
/\/
G○H○○I
\
○J
6.15：
答：
分别在前序线索二叉树和后序线索二叉树中查找前趋和后继时，线索无帮助作用。
6.16：
解：
（1）（a）的前序序列：
ABCDEF后序序列：
BDEFCA
（b）的前序序列：
GHIJK后序序列：
IJKHG
（c）的前序序列：
LMPQRNO后序序列：
QRPMNOL
（2）此森林的前序序列：
ABCDEFGHIJKLMPQRNO
此森林的后序序列：
BDEFCAIJKHGQRPMNOL
（3）此森林转化为二叉树的过程见动画：
6.17：
解：
各二叉树所对应森林如下：
-----------------------------
（a）○A
-----------------------------
（b）○A
｜
○B
｜
○C
-----------------------------
（c）○A○B○C
-----------------------------
（d）○A○C
/
○B
-----------------------------------------------
（e）○A○C○F○I
/\/
○B○E○L
/|\
○D○H○K
/|
○G○J
6.18答：
所谓严格二叉树是指该树中没有度数为1的分支结点的二叉树。
所以：
高度为h的的严格二叉树至少有2h-1个结点；至多有2^h-1个结点（即满二叉树）。
6.19答，在每个字符的使用概率相同的情况下，也即在哈夫曼树中每片叶子的权重相等的时候，等长编码是最优的前缀码。
6.20答：
第二组不是前缀码。
因为0，1分别是00和11的前缀。
（前缀码是指该编码集中的任一编码不是其他编码的前缀）
注意：
哈夫曼编码不一定是相同的，这和具体的算法有关，或者说是你画的树有关.但有一条原则，每次合并的均是当前最小的两个值，合并后要重新排序。
最后你可以选左枝或右枝为0来编码。
任一个具体的哈夫曼算法都会得到平均码长最短且相等编码集（虽然具体编码可能不同）。
6.21解：
哈夫曼编码图见题图
根据上图可得编码表：
a:
0010
b:
10
c:
00000
d:
0001
e:
01
f:
00001
g:
11
h:
0011
（2）用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为：
4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61
2.61/3=0.87=87%
其平均码长是等长码的87%。
所以平均压缩率为13%。
*6.22解：
这个函数如下：
voidPrintNode（BinTreeT）
{
printf（"%c",T->data）;
}
为了验证这个函数是否正确，要先建立一棵二叉树,然后调用这个中序遍历算法
------------------------------------------------------
//定义二叉树链式存储结构
typedefcharDataType;//定义DataType类型
typedefstructnode{
DataTypedata;
structnode*lchild,*rchild;//左右孩子子树
}BinTNode;//结点类型
typedefBinTNode*BinTree;//二叉树类型
#include
#include
voidCreatBinTree（BinTree*T）//输入序列是先序序列
{//构造二叉链表。
T是指向根的指针，故修改了*T就修改了实参
charch;
if（（ch=getchar（））==''）
*T=NULL;
else{//读入非空格
*T=（BinTNode*）malloc（sizeof（BinTNode））;//生成结点
（*T）->data=ch;
CreatBinTree（&（*T）->lchild）;//构造左子树
CreatBinTree（&（*T）->rchild）;//构造右子树
}
}
//--------------------------------
voidPrintNode（DataTypex）
{//题目要求的打印函数
printf（"%c",x）;
}
//--------------------------------
voidInorder（BinTreeT,void（*Visit）（DataTypex））
{
if（T）
{
Inorder（T->lchild,Visit）;//遍历左子树
Visit（T->data）;//通过函数指针调用它所指的函数访问结点
Inorder（T->rchild,Visit）;//遍历右子树
}
}
voidmain（）
{//现在开始测试啦
BinTreeroot;//定义一个根结点
CreatBinTree（&root）;//建立二叉链表
printf（"\n"）;
Inorder（root,PrintNode）;//调用函数,注意传递的是函数名（它就是地址）
printf（"\n"）;
}
//运行时请输入"abc"（注意b后和c后面各两个空格）再回车，可生成一个以a为根的两片叶子的二叉树，看看打印的结果对不对?
6.23解：
利用中序遍历，我们很容易地就能找到这个算法每访问一次非空结点就给变量nodes加上1;每访问到一个其左右子树皆空的结点就给变量leaves加上1，最后就得到结果了：
完整程序如下所示：
//定义二叉树链式存储结构等内容，为方便起见我们将这一段内容存为bintree.h文件，以后只在程序中加入这个头文件就是了。
//------------bintree.h文件开始--------------
typedefcharDataType;//定义DataType类型
typedefstructnode{
DataTypedata;
structnode*lchild,*rchild;//左右孩子子树
}BinTNode;//结点类型
typedefBinTNode*BinTree;//二叉树类型
#include
#include
voidCreatBinTree（BinTree*T）
{//构造二叉链表,注意:
输入序列是先序序列
charch;
if（（ch=getchar（））==''）
*T=NULL;
else{//读入非空格
*T=（BinTNode*）malloc（sizeof（BinTNode））;//生成结点
（*T）->data=ch;
CreatBinTree（&（*T）->lchild）;//构造左子树
CreatBinTree（&（*T）->rchild）;//构造右子树
}
}//------------------文件结束---------------------
//------------以下两个函数为题目要求算法------------
intNode（BinTreeT）
{//算结点数
intstaticnodes=0;//静态变量保留每次递归调用后的值
if（T）
{//使用中序遍历
Node（T->lchild）;//遍历左子树
nodes++;//结点数加1
Node（T->rchild）;//遍历右子树
}
returnnodes;
}
intLeaf（BinTreeT）
{//算叶子数
intstaticleaves=0;//静态变量保证其值不会随递归调用而消失
if（T）
{//使用中序遍历
Leaf（T->lchild）;//遍历左子树
if（!
（T->lchild||T->rchild））//左右孩子均为空
leaves++;//叶子数加1
Leaf（T->rchil
升级会员 