严蔚敏++数据结构习题集答案(3)

（2） 空二叉树或任一结点均无左子树的非空二叉树 （3） 空二叉树或仅有一个结点的二叉树 （4） 同（3）

6．10 试采用顺序存储方法和链接存储方法分别画出6. 30所示各二叉树的存储结构。 解：①顺序存储：

(a)1 2 φφ 3 φ φ φ φ 4 φ φ φ φ φ φ φ φ φ φ 5

(b)1 φ 2 φ φ 3 φ φ φ φ φ φ φ 4 φ φ φ φ φ φ φ φ φ φ φ φ 5

(c)1 φ 2 φ φ 3 4 φ φ φ φ 5 6 φ φ φ φ φ φ φ φ φ φ φ 7 8 (d)1 2 3 4 φ 5 6 φ 7 φ φ φ φ 8 9 ②连接存储：

6．11 分别写出图6.30所示各二叉树的前序、中序和后序序列。 解：

6．12 若二叉树中个结点的值均不相同，则由二叉树的前序序列和中序序列，或由其后序序列的中序列均能惟一地确定一棵二叉树，但由前序序列和后序序列却不一定能惟一地确定一棵二叉树。

（1） 已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF，请画

出此二叉树。

（2） 已知一棵二叉树的中序序列和后序序列分别为BDCEAFHG和DECBHGFA，请画出

此二叉树。

（3） 已知两棵二叉树前序序列和后序序列均为AB和BA，请画出这两棵不同的二叉树。 解：

6．13 对二叉树中结点进行按层次顺序（每一层自左至右）的访问操作称为二叉树的层次遍历，遍历所得到的结点序列称为二叉树的层次序列。现已知一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF，请画出该二叉树。 解：

6．14 试画出图6.30所示各二叉树的前序、中序和后序线索树及相应的线索链表。 解：

（以c为例）

① 前序：1 2 3 5 7 8 6 4 ② 前序：1 7 5 8 3 6 2 4

6．15 在何种线索树中，线索对所求指定结点在相应次序下的前趋和后继并无帮助？ 解：

在前序线索树中找某一点的前序前趋以及在后序线索树中寻找某一点的后继，线索并无多大帮助。

6．16 对图6.31所示的森林：

（1） 求各树的前序序列和后序序列： （2） 求森林的前序序列和后序序列： （3） 将此森林转换为相应的二叉树：

（4） 给出（a）所示树的双亲链表表示、孩子链表表示、双亲孩子链表表示及孩子兄

弟链表表示等四种存储结构，并指出哪些存储结构易于求指定结点的祖先，哪些易于求指定结点的后代？

解：

(1) a b c

前序 ABCDEF GHIJK LMPQRNO 后序 BDEFCA IJKHG QRPMNOL (2) 前序： ABCDEFGHIGKLMPQRNO 后序： BDEFCAIJKHGQRPMNOL

(3) 二叉树 (4) 1

① 孩子链表表示发：

② 双亲链表表示发：

结点 0 1 2 3 4 5 6 data A B C D E F parent -1 0 1 1 3 3 3

③ 双亲孩子链表： ④ 孩子兄弟链表表示： ⑤ 易于求祖先：双亲链表面 双亲孩子 ⑥ 易于求后代：孩子链表 双亲孩子

6．17 画出图6.32所示的各二叉树所应的森林

6．18 高度为h的严格二叉树至少有多少个结点？至多有多少个结点？ 解：

最多有2n-1 最少有 2n-1

6．19 在什么样的情况下，等长编码是最优的前缀码？ 解：

当字符集中的各字符使用频率均匀时。 6．20 下属编码哪一组不是前缀码？

{00，01，10，11}，{0，1，00，11}，{0，10，110，111} 解：

因为前缀码中不可能存在一个元素是另一个的前面部分。 所以第二组不是。

6．20 假设用于通信的电子由字符集{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个字母进行等长编码，则哈夫曼编码的平均

码长是等长编码的百分之几？它使电文总长平均压缩多少？

解：

① ②哈夫曼编码码长：

4*0.07+2*0.19+5*0.02+4*0.06+5*0.03+2*0.21+4*0.1=2.71 等长码长： 3

905 平均缩了10%

（二） 算法设计题

6.22 二叉树的遍历算法可写为通用形式。例如，通用的中序遍历为：

void Inorder(BinTree T,void(*Visit)(Datatype x)) { if (T)

{Inorder(T->lchild,Visit); /*遍历左子树*/

Visit(T->data); /*通过函数指针调用它所指的函数来访问结点*/ Inorder(T->rchild,Visit); /*遍历右子树*/ } }

其中Visit是一个函数指针，它指向形如void f（DdataType x）的函数。因此我们可以将访问结点的操作写在函数f中，通过调用语句Inorder（root，f）将f的地址传递给Visit，来执行遍历操作。请写一个打印结点的数据的函数，通过调用上述算法来完成书中6.3节的中序遍历。

解：

#include“stdio.h” #define Null 0

typedef char DataType; typedef struct node {

DataType data;

Struct node lchild,rchild;

}BinTree; BinTree *root; BinTree *Q[100];

BinTree CreateBinTree() /*建立二叉树*/ {

char ch;

int front,rear; BinTree root,s; Root=Null; front=1; rear=0;

ch=getchar(); while(ch!=’#’) {

s=Null;

if(ch!=’@’) {

s=(BinTree*)malloc(sizeof(BinTree)); s->data=ch; s->lchild=Null; s->rchild=Null; }

rear ++; Q[rear]=s;

if(rear==1) root=s; else {

if(s&&Q[front])

if(rear%2==0) Q[front]->lchild=s; else

Q[front]->rchild=s; if(rear%2==1) front++; }

ch=getchar(); }

return root; }

main() {

root=CreateBinTree(); Inorder(root); }

① 中序遍历法之一

Inorder(BinTree *t) {

if(t) {

Inorder(t->lchild); Visit(t->data);

Inorder(t->rchild); } }

Vist(int i) {

printf(“%c”,i); }

② 中序遍历法之二

Inorder(BinTree *t) {

if(t) {

Inorder(t->lchild); printf(“%c”,t->data); Inorder(t->rchild); } }

6.23 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。 解：

① 计算结点总数

int CountNode(BinTree *root) {

int num1,num2;

if(root==Null) return(0);

else if(root->lchild==Null&&rooot->rchild==Null) return(1); else {

num1=CountNode(roo …… 此处隐藏：2675字，全部文档内容请下载后查看。喜欢就下载吧 ……