数据结构（C语言版）习题解答

A B C D E F G H I J K 图6-1

先根遍历：ABCEIJFGKHD 后根遍历：BIJEFKGHCDA

对应的二叉树：

A B C E D I F J G K H 6.9 将如图6-2所示的森林转化为对应的二叉树。

A B I J K M L N C D E F G H 树对应的二叉树

A B C D E F H G

森林对应的二叉树：

6-2

I J K 图6-2

O L M N O 图

A B C D L E F H G M N O

I J K

6.11已知某二叉树的中序序列为DCBGEAHFIJK，后序序列为DCEGBFHKJIA。请画出该二叉树。

A B C D G E I H F J K

6.14 假设某个电文由(a,b,c,d,e,f,g,h)8个字母组成，每个字母在电文中出现的次数分别为(7,19,2,6,32,3,21,10)，试解答下列问题： (1) 画出出huffman树；

1000 60 28 11 G 40 19b 21g 5 2c 3f 17 6d 7a 10h 32e

(2) 写出每个字母的huffman编码；

a:1010 b:00 c:10000 d:1001 e:11 f:10001 g:01 h:1011 (3) 在对该电文进行最优二进制编码处理后，电文的二进制位数。 4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=261 6.17 写出按层次遍历二叉树的算法。 思路：用队列存储结构，并用递归方法

Status LevelOrderTraverse(BitTree T,Status (*Visit)(TElemType e)//层序遍历二叉树

{

InitQueue(Q); //初始化队列

if(!T) return Error;//空树，直接返回 EnQueue(Q,T);//根结点入队 BiTNode *p;

while(!QueueEmpty(Q)) {

DeQueue(Q,p); Visit(p->data);

if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }//while return Ok;

}//LevelOrderTraverse

6.19 写出判断两棵给定二叉树是否相似的算法。

(注：两棵二叉树B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似。)