4、树内各结点度的最大值称为树的度。 四、代码填空题
1、函数InOrderTraverse(Bitree bt)实现二叉树的中序遍历，请在空格处将算法补充完整。
void InOrderTraverse(BiTree bt){ if(){
InOrderTraverse(bt->lchild); printf(“%c”,bt->data); ; } }
2、函数depth实现返回二叉树的高度，请在空格处将算法补充完整。 int depth(Bitree *t){ if(t==NULL) return 0; else{
hl=depth(t->lchild);
}
hr=depth(t->rchild); 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）哪个结点是根结点？ （2）哪些结点是叶子结点？ （3）哪些结点是k的祖先？ （4）哪些结点是j的兄弟？ （5）树的深度是多少？。
2、假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
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个字母设计哈夫曼编码。
10001B 101A 00038010621C 10000170121G032301ED 1001E 11F 10001G 01H 0017A10H01116D19B50123CF答案：
4、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。
答案：二叉树形态
ABCEDFGH
5、试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。 答案：
301218743125116
WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69
6、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。 答案：(1)树形态：
321367919105523
(2)带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79
7、已知一棵二叉树的先序序列：ABDGJEHCFIKL；中序序列：DJGBEHACKILF。画出二叉树的形态。
ABDGJEHKILCF答案：
8、一份电文中有6种字符：A,B,C,D,E,F，它们的出现频率依次为16，5，9，3，30，1，完成问题：
（1）设计一棵哈夫曼树；（画出其树结构） （2）计算其带权路径长度WPL； 答案：(1)树形态：
6430341618995413
(2)带权路径长度：WPL=30*1+16*2+9*3+5*4+(1+3)*5=30+32+27+20+20=129
9、已知某森林的二叉树如下所示，试画出它所表示的森林。
ABCEDHFG
DCEGFH答案：
AB
10、有一分电文共使用5个字符;a,b,c,d,e，它们的出现频率依次为4、7、5、2、9，试构造哈夫曼树，并给出每个字符的哈夫曼编码。
11、画出与下图所示的森林相对应的二叉树，并指出森林中的叶子结点在二叉树中具有什么特点。
ABCDIJNEFGKLMH