答案：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。
六、算法设计题（前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); }
法二：
intLeafCount_BiTree(Bitree T)//求二叉树中叶子结点的数目 {
if(!T) return 0; //空树没有叶子
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
typedefstructliuyu{intdata;structliuyu *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); } return(0); }
main() /*先生成二叉排序树，再调用中序遍历递归函数进行排序输出*/ {inti,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) /*统计层数*/
{intd,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; }
p=p+1; return(p); }
法二：
intGet_Sub_Depth(BitreeT,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
intGet_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 817 2 11 16 21 4 9 13
步骤2：执行求深度的函数，并打印统计出来的深度值。 完整程序如下： #include
typedefstructliuyu{intdata;structliuyu *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
int depth(liuyu*root) /*统计深度*/
{intd,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; }
p=p+1; return(p); }
void main() /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/
{inti,x; i=1;
root=NULL; /*千万别忘了赋初值给root!*/ do{printf(\i++;
scanf(\ /*从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){
printf(\ else insert_data(x);} /*调用插入数据元素的函数*/ while(x!=-9999); return;} 执行结果：
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库《c语言数据结构》第6章 树和二叉树 自测卷解答(2)在线全文阅读。
相关推荐：