}BT;
int count=0;
void Leafnum(BT *T) {
if (T!=NULL)
{ if(T->lchild==NULL && T->rchild==NULL) count++;
Leafnum(T->lchild); Leafnum(T->rchild); } }
解：3 （求叶结点数） (2，3，4改为程序填空)
二． 程序填空
1．填空完成二叉树按层次遍历的程序
typedef struct BT
{ datatype data; // 定义结点 BT *lchild; BT *rchild; }BT;
void Levelorder(BT *T) // 层次遍历 { int i,j;
BT *q[100],*p; p=T;
if ( p!=NULL )
{ i=1;q[i]=p;j=2; } while (i!=j)
{ p=q[i];
cout<< p->data ;
if ( p->lchild!=NULL )
{ q[j]= p->lchild ;j++;} if (p->rchild!=NULL)
{ q[j]= p->rchild ;j++; } i++; }
}
}
17
三． 应用题
1． 将下列二叉树转换为森林。
A
C B
D E F G
J I H
K
解： A G C B E J K F D I H
2． 画出和下列二叉树相应的森林。 解： A C F I E B M
D H K
G J
（根右边的子树肯定是森林，而孩子结点的右子树均为兄弟）
18
3． 某二叉树的结点数据采用顺序存储，其结构如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 E A F D H C G I B （1）画出该二叉树（2分）
（2）写出结点值为D的父结点及左、右子树（3分） 解： （1）
E
A F
H D
C I G
B
（2） D的父结点为A
D的左子树为C D的右子树为空
4． 某二叉树的存储如下： 1 2 3 Lchild Data Rchild 0 J 0 0 H 0 2 F 0 4 3 D 9 5 7 B 4 6 5 A 0 7 8 C 0 8 0 E 0 9 10 G 0 10 1 I 0 其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为数据域。 （1）画出该二叉树（3分）
（2）写出该树的中序遍历的结点序列（2分） 解：
（1） A （2）中序遍历的结点序列：
E C B H F D J I G A
B
C D
E F G
H I J
19
5． 某二叉树的存储如下： lchild Data rchild 1 0 J 0 2 0 H 0 3 2 F 0 4 3 D 9 5 7 B 4 6 5 A 0 7 8 C 0 8 0 E 0 9 10 G 0 10 1 I 0 其中根结点的指针为6，lchild、rchild分别为结点的左、右孩子的指针域，data为数据域。 （1）画出该二叉树（3分）
（2）写出该树的后序遍历的结点序列（2分） 解：
A （1）
B
C D
E F G H I
J
（2）后序遍历的结点序列：E C H F J I G D B A
6． 已知一棵二叉树结点的中序遍历序列为：DEBAFCHG，后序遍历序列：EDBFHGCA，试恢复该二叉树，并写出它的先序遍历的序列。
解：恢复的二叉树
A
B C G D F E H
先序遍历序列为：A B D E C F G H
7． 已知一棵二叉树的后序遍历序列为：ACDBGIHFE，中序遍历序列为：ABCDEFGHI，试恢复该二叉树，并写出它的层次遍历的序列。
20