3.【严题集6.17③】阅读下列算法，若有错，改正之。 答：这是找结点后继的程序。 共有3处错误。 注：当rtag＝1时说明内装后继指针，可直接返回，第一句无错。 当rtag＝0时说明内装右孩子指针，但孩子未必是后继，需要计算。中序遍历应当先左再根再右，所以应当找左子树直到叶子处。r=r->lchild; 直到LTag=1； 应改为：while(!r->Ltag)r=r->Lchild; BiTree InSucc(BiTree q){ //已知q是指向中序线索二叉树上某个结点的指针， //本函数返回指向*q的后继的指针。 r=q->rchild; //应改为r=q； if(!r->rtag) while(!r->rtag)r=r->rchild; //应改为 while(!r->Ltag) r=r->Lchild; return r; //应改为return r->rchild；
4.【严题集6.21②】画出和下列二叉树相应的森林。
答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。
六、算法设计题（前5题中任选2题，第6题必做，每题8分，共24分）
1.【严题集6.42③】编写递归算法，计算二叉树中叶子结点的数目。
解：思路：输出叶子结点比较简单，用任何一种遍历递归算法，凡是左右指针均空者，则为叶子，将其打印出来。
法一：核心部分为：
DLR(liuyu *root) /*先序遍历 递归函数*/ {if(root!=NULL)
{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf(\ DLR(root->lchild); DLR(root->rchild); } return(0); }
法二：
int LeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 {
if(!T) return 0; //空树没有叶子
5
else if(!T->lchild&&!T->rchild) return 1; //叶子结点
else return Leaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加 上右子树的叶子数 }//LeafCount_BiTree
注：上机时要先建树！例如实验二的方案一。 ① 打印叶子结点值（并求总数）
思路：先建树，再从遍历过程中打印结点值并统计。
步骤1 键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。叶子结点值应该是4，9, 13, 21, 总数应该是4. 12
7 17 2 11 16 21 4 9 13
编程： 生成二叉树排序树之后，再中序遍历排序查找结点的完整程序如下： 说明部分为： #include
typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test; liuyu *root;
int sum=0;int m=sizeof(test);
void insert_data(int x) /*如何生成二叉排序树？参见教材P43C程序*/ { liuyu *p,*q,*s; s=(test*)malloc(m); s->data=x;
s->lchild=NULL; s->rchild=NULL;
if(!root){root=s; return;} p=root;
while(p) /*如何接入二叉排序树的适当位置*/ {q=p;
if(p->data==x){printf(\else if(x
if(x
DLR(liuyu *root) /*中序遍历 递归函数*/ {if(root!=NULL)
{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf(\ DLR(root->lchild); DLR(root->rchild); }
6
return(0); }
main() /*先生成二叉排序树，再调用中序遍历递归函数进行排序输出*/ {int i,x; i=1;
root=NULL; /*千万别忘了赋初值给root!*/ do{printf(\i++;
scanf(\ /*从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){ DLR(root);
printf(\ return(0); }
else insert_data(x);} /*调用插入数据元素的函数*/ while(x!=-9999); return(0);} 执行结果：
若一开始运行就输入-9999，则无叶子输出，sum=0。
2.【全国专升本统考题】写出求二叉树深度的算法，先定义二叉树的抽象数据类型。 （10分） 或【严题集6.44④】编写递归算法，求二叉树中以元素值为x的结点为根的子树的深度。
答；设计思路：只查后继链表指针，若左或右孩子的左或右指针非空，则层次数加1；否则函数返回。 但注意，递归时应当从叶子开始向上计数，否则不易确定层数。 int depth(liuyu*root) /*统计层数*/
{int d,p; /*注意每一层的局部变量d,p都是各自独立的*/ p=0;
if(root==NULL)return(p); /*找到叶子之后才开始统计*/ else{
d=depth(root->lchild);
if(d>p) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild); if(d>p)p=d; }
7
p=p+1; return(p); }
法二：
int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 {
if(T->data==x) {
printf(\找到了值为x的结点,求其深度 exit 1; } } else {
if(T->lchild) Get_Sub_Depth(T->lchild,x);
if(T->rchild) Get_Sub_Depth(T->rchild,x); //在左右子树中继续寻找 }
}//Get_Sub_Depth
int Get_Depth(Bitree T)//求子树深度的递归算法 {
if(!T) return 0; else {
m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1; }
}//Get_Depth
附：上机调试过程
步骤1 键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。层数应当为4
12 8 17 2 11 16 21 4 9 13
步骤2： 执行求深度的函数，并打印统计出来的深度值。 完整程序如下： #include
typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test; liuyu *root;
int sum=0;int m=sizeof(test);
8
