数据结构课后习题及解析六.docx
《数据结构课后习题及解析六.docx》由会员分享，可在线阅读，更多相关《数据结构课后习题及解析六.docx（20页珍藏版）》请在冰点文库上搜索。
数据结构课后习题及解析六
第六章习题
1.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2.对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3.已知一棵度为k的树中有ni个度为1的结点，n2个度为2的结点，…；nk个度为k的结点，则该树中有多少个叶子结点并证明之。
4.假设一棵二叉树的先序序列为EBADCFHGIKJ中序序列为ABCDEFGHIJK请画出该二叉树。
5.已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？
6.给出满足下列条件的所有二叉树：
1前序和后序相同
2中序和后序相同
3前序和后序相同
7.n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？
8.画出与下列已知序列对应的树T:
树的先根次序访问序列为GFKDAIEBCHJ
树的后根次序访问序列为DIAEKFCJHBG
9.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：
0.07,0.19，0.02，0.06，0.32，0.03，0.21，0.10
请为这8个字母设计哈夫曼编码。
10.已知二叉树采用二叉链表存放，要求返回二叉树T的后序序列中的第一个结点指针，是否可不用递归且不用栈来完成？
请简述原因.
11.画出和下列树对应的二叉树:
12•已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13•编写递归算法：
对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
14•分别写函数完成：
在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。
在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
15•分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。
16•编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
17•对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18•已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。
19.设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。
正则二叉树是指：
在二叉树中不存在子树个数为1的结点。
20.计算二叉树最大宽度的算法。
二叉树的最大宽度是指：
二叉树所有层中结点个数的最大值。
21.已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
22.证明：
给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；
给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；
23.二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
24.二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。
实习题
1.［问题描述］建立一棵用二叉链表方式存储的二叉树，并对其进行遍历＜先序、中序和后
序），打印输出遍历结果。
［基本要求］从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树＜以先序来建立）
并对其进行遍历＜先序、中序、后序），然后将遍历结果打印输出。
要求采用递归和非递归两种方法实现。
［测试数据］ABC巾巾D邱G巾巾F巾巾巾＜其中巾表示空格字符）
输出结果为：
先序：
ABCDEGF
中序：
CBEGDFA后序：
CGBFDBA
2•已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示＜竖向显示就是二
叉树的按层显示）。
3•如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如下图所示。
2.按凹入表形式打印树形结构，如下图所示
A
B
E
F
C
G
D
第六章答案
6.1分别画出具有3个结点的树和3个结点的二叉树的所有不同形态
【解答】
具有3个结点的树具有3个结点的二叉树
6.3已知一棵度为k的树中有ni个度为1的结点，n2个度为2的结点，……,nk个度为k的结点，则该树中有多少个叶子结点？
【解答】设树中结点总数为n,则n=n°+ni++rk
树中分支数目为B,则B=ni+2n2+3n3++kn
因为除根结点外，每个结点均对应一个进入它的分支，所以有n=B+1
即no+ni++nk=ni+2n2+3n3++krk+1
由上式可得叶子结点数为：
no=n2+2n3++（k-i＞nk+i
6.5已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？
【解答】no表示叶子结点数，n2表示度为2的结点数，贝Uno=n2+i
所以n2=no-i=49，当二叉树中没有度为i的结点时，总结点数n=no+n2=99
6.6试分别找出满足以下条件的所有二叉树：
（i＞前序序列与中序序列相同。
（2＞中序序列与后序序列相同。
（3＞前序序列与后序序列相同。
【解答】
（i＞前序与中序相同：
空树或缺左子树的单支树；
（2＞中序与后序相同：
空树或缺右子树的单支树；
（3＞前序与后序相同：
空树或只有根结点的二叉树。
6.9假设通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：
o.o7，o.i9，o.o2，o.o6，o.32，o.o3，o.2i，o.io
请为这8个字母设计哈夫曼编码。
【解答】
构造哈夫曼树如下:
IlJU
哈夫曼编码为：
11：
11111
I5：
1100
丨2：
11110
I6：
10
I3：
1110
I7:
01
丨4：
1101
I8:
00
6.11画出如下图所示树对应的二叉树
6.15分别写出算法，实现在中序线索二叉树T中查找给定结点*p在中序序列中的前驱与后继。
在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。
在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
<1）找结点的中序前驱结点
BiTNode*lnPre（BiTNode*p>
/*在中序线索二叉树中查找p的中序前驱结点，并用pre指针返回结果*/
{if（p->Ltag==1>pre=p->LChild。
/*直接利用线索*/
else
{/*在p的左子树中查找“最右下端”结点*/
for（q=p->LChild。
q->Rtag==0。
q=q->RChild>。
pre=q。
}
return（pre>。
<2）找结点的中序后继结点
BiTNode*lnSucc（BiTNode*p>
/*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/
{if（p->Rtag==1>succ=p->RChild。
/*直接利用线索*/
else
{/*在p的右子树中查找“最左下端”结点*/
for（q=p->RChild。
q->Ltag==0。
q=q->LChild>。
succ=q。
}
return（succ>。
}
（3>找结点的先序后继结点
BiTNode*PreSucc（BiTNode*p>
/*在先序线索二叉树中查找p的先序后继结点，并用succ指针返回结果*/
{if（p->Ltag==0>succ=p->LChild。
elsesucc=p->RChild。
return（succ>。
}
（4>找结点的后序前驱结点
BiTNode*SuccPre（BiTNode*p>
/*在后序线索二叉树中查找p的后序前驱结点，并用pre指针返回结果*/
{if（p->Ltag==1>pre=p->LChild。
elsepre=p->RChild。
return（pre>。
个人资料整理―仅限学习使用一
6.21已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法
【解答】
VoidPreOrder（BiTreeroot>/*先序遍历二叉树的非递归算法*/
{
InitStack（&S>。
p=root。
while（p!
=NULL||!
lsEmpty（S>>
{if（p!
=NULL>
{
Visit（p->data>。
push（&S,p>。
p=p->Lchild。
}
else
{
Pop（&S,&p>。
p=p->RChild。
}
}
}
6.24已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。
【解答】
算法（一>
Voidexchange（BiTreeroot>
p=root。
个△资料整理
if（p->LChild!
=NULL||p->RChild!
=NULL>
{
temp=p->LChild。
p->LChild=p->RChild。
p->RChild=temp。
exchange（p->LChild>。
exchange（p->RChild>。
}
}
算法（二>
Voidexchange（BiTreeroot>
{
p=root。
if（p->LChild!
=NULL||p->RChild!
=NULL>
{
exchange（p->LChild>。
exchange（p->RChild>。
temp=p->LChild。
p->LChild=p->RChild。
p->RChild=temp。
}
}
第六章习题解读
1.试分别画出具有3个结点的树和3个结点的二叉树的所有不同形
2.对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。
3.已知一棵度为k的树中有ni个度为1的结点，“2个度为2的结点，……,nk个度为k的结点，则该树中有多少个叶子结点？
［提示］:
参考P.116性质3
n=n°+“1++nk
B=n1+2n2+3n3++knk
n=B+1
no+n1++nk=n1+2n2+3n3++knk+1
n0=n2+2n3++（k-1>nk+1
4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为
ABCDEFGHIJK，请画出该二叉树。
［提示］:
参考P.148
6.已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多
少个？
［提示］:
［方法1］
个人资料整理―仅限学习使用一
<1）一个叶子结点，总结点数至多有多少个？
结论：
可压缩一度结点。
<2）满二叉树或完全二叉树具有最少的一度结点
<3）可能的最大满二叉树是几层？
有多少叶结点？
如何增补?
25<50<26
可能的最大满二叉树是6层
有25=32个叶结点
假设将其中x个变为2度结点后，总叶结点数目为50
贝2x+（32-x>=50
得：
x=18
此时总结点数目=（26-1>+18X2
[方法2]
假设完全二叉树的最大非叶结点编号为m,
则最大叶结点编号为2m+1,
（2m+1>-m=50
m=49总结点数目=2m+仁99
［方法3］
由性质3:
n°=n2+1
即：
50=n2+1
所以：
“2=49
令比=0得：
n=n0+n2=99
7.给出满足下列条件的所有二叉树：
a＞前序和中序相同
b＞中序和后序相同
c＞前序和后序相同
［提示］:
去异存同。
a＞DLR与LDR的相同点：
DR，如果无L，则完全相同，如果无
LR，…。
b＞LDR与LRD的相同点：
LD，如果无R，则完全相同。
c＞DLR与LRD的相同点：
D，如果无LR,则完全相同。
＜如果去D，则为空树）
7.n个结点的K叉树，若用具有k个child域的等长链结点存储树的
一个结点，则空的Child域有多少个？
［提示］:
参考P.119
个人资料整理―仅限学习使用一
8.画出与下列已知序列对应的树T:
树的先根次序访问序列为GFKDAIEBCHJ;
树的后根次序访问序列为DIAEKFCJHBG。
［提示］:
<1）先画出对应的二叉树
<2）树的后根序列与对应二叉树的中序序列相同
9.假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率
分别为：
0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10
<1）请为这8个字母设计哈夫曼编码，
<2）求平均编码长度。
10.已知二叉树采用二叉链表存放，要求返回二叉树T的后序序列中的
第一个结点的指针，是否可不用递归且不用栈来完成？
请简述原因.
［提示］:
无右子的“左下端”11.画出和下列树对应的二叉树:
12.已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13.编写递归算法：
对于二叉树中每一个元素值为x的结点，删去以它
为根的子树，并释放相应的空间。
［提示］:
［方法1］:
<1）按先序查找；<2）超前查看子结点<3）按后序释放；
voidDelSubTree（BiTree*bt,DataTypex>
{
if（*bt!
=NULL&&（*bt>->data==x>
{FreeTree（*bt>。
*bt=NULL。
elseDelTree（*bt,x>
voidDelTree（BiTreebt,DataTypex>
{if（bt>
{if（bt->LChild&&bt->LChild->data==x>
{FreeTree（bt->LChild>。
bt->LChild=NULL。
}
if（bt->RChild&&bt->RChild->data==x>
{FreeTree（bt->RChild>。
bt->RChild=NULL。
DelTree（bt->LChild,x>。
DelTree（bt->RChild,x>。
［方法2］:
<1）先序查找；<2）直接查看当前根结点<3）用指针参数;
［方法3］:
<1）先序查找；<2）直接查看当前根结点
<3）通过函数值，返回删除后结果；
<参示例程序）
14.分别写函数完成：
在先序线索二叉树T中，查找给定结点*p在先
序序列中的后继。
在后序线索二叉树T中，查找给定结点*p在后序序列
中的前驱。
［提示］:
<1）先查看线索，无线索时用下面规律：
<2）结点*p在先序序列中的后继为其左子或右子；
<3）结点*p在后序序列中的前驱也是其左子或右子。
15.分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序
列中的前驱与后继。
<参例题）
16.编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
［提示］:
<1）可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理
<2）可利用返回值，或全局变量。
17.对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18.已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。
<参课本）
19.设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则
二叉树。
正则二叉树是指：
在二叉树中不存在子树个数为1的结点。
［提示］:
可利用任何递归、非递归遍历算法。
20.计算二叉树最大宽度的算法。
二叉树的最大宽度是指：
二叉树所有层中结点个数的最大值。
21.已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。
22.证明：
给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二
叉树；
给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树;
23.二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。
实习题
1.［问题描述］
建立一棵用二叉链表方式存储的二叉树，并对其进行遍历<先序、中
序和后序），打印输出遍历结果。
［基本要求］
从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树V以
先序来建立）并对其进行遍历V先序、中序、后序），然后将遍历结果打印输出。
要求采用递归和非递归两种方法实现。
［测试数据］ABC巾4DE巾G巾折巾巾巾其中巾表示空格字符）
输出结果为：
先序：
ABCDEGF
中序：
CBEGDFA
后序：
CGBFDBA
2.已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的
竖向显示V竖向显示就是二叉树的按层显示）。
［提示］:
<1）参习题6.20,实现逐层遍历
<2）队中保存每个结点的打印位置，其左、右子的距离
3.如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如图
6.34所示。
图6.34
4.按凹入表形式打印树形结构，如图6.35所示［提示］:
参P.129例，用先根遍历
A
B
E
F
C
G
D
升级会员 