if( hl>hr ) return hl+1;
else
return hr+1;
}
}
3、写出下面算法的功能。
Bitree *function(Bitree *bt){
Bitree *t,*t1,*t2; if(bt==NULL)
t=NULL;
else{
t=(Bitree *)malloc(sizeof(Bitree)); t->data=bt->data;
t1=function(bt->left); t2=function(bt->right); t->left=t2; t->right=t1;
}
return(t);
} 答案：交换二叉树结点左右子树的递归算法 4、写出下面算法的功能。
void function(Bitree *t){
if(p!=NULL){
function(p->lchild); function(p->rchild);
printf( “%d” ,p->data);
}
} 答案：二叉树后序遍历递归算法 五、综合题
1、假设以有序对
（ 1）哪个结点是根结点？ a
（ 2）哪些结点是叶子结点？ b,d,i,j,f,k,h （ 3）哪些结点是 k 的祖先？ g,c,a （ 4）哪些结点是 j 的兄弟？ i （ 5）树的深度是多少？ 4
2、假设一棵二叉树的先序序列为 EBADCFHGIKJ，中序序列为 ABCDEFGHIJK，请画出该二叉树。
25
【知识点：二叉树前序序列的隐含性质：第一个一定是二叉树的根，后面紧跟着的是其左子树的根；二叉树后序序列的隐含性质：最后一个一定是二叉树的根，它的紧前一个是其右子树的根 】 答案：
3、假设用于通讯的电文仅由 8 个字母 A、B、C、D、E、F、G、H组成，字母在电文中出现的频率分别为： 0.07 ，0.19 ，0.02 ，0.06 ，0.32 ， 0.03 ， 0.21 ， 0.10 。请为这 8 个字母设计哈夫曼编码。
26
答案：
4、已知二叉树的先序遍历序列为 ABCDEFGH，中序遍历序列为 CBEDFAGH，画出二叉
树。答案：二叉树形态
A
12
30
B G
C D H
E F
5、试用权集合 {12,4,5,6,1,2} 答案：
构造哈夫曼树，并计算哈夫曼树的带权路径长度。
1
7
18
11
4
3 2
5 6
WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69
6、已知权值集合为 {5,7,2,3,6,9} ，要求给出哈夫曼树，并计算带权路径长度 答案： (1) 树形态：
27
WPL。
32
13
6
19
7 9
10 5
2
5
3
(2) 带权路径长度： WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79
7、已知一棵二叉树的先序序列： ABDGJEHCFIKL；中序序列： DJGBEHACKILF。画出二叉树的形态。
A
B C
D E F
G H
I
答案：
J K L
8、一份电文中有 6 种字符： A,B,C,D,E,F ，它们的出现频率依次为 16，5，9，3，30， 1，完成问题：
（ 1）设计一棵哈夫曼树；（画出其树结构） （ 2）计算其带权路径长度 WPL； 答案： (1) 树形态：
64
30
34
16
18 9
9 5
4
1 3
(2) 带权路径长度： WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129 9、已知某森林的二叉树如下所示，试画出它所表示的森林。
28
