内容发布更新时间 : 2024/11/15 23:36:59星期一 下面是文章的全部内容请认真阅读。
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的左、右子树分别相似。)