数据结构 第6章习题答案

12

7 17 2 11 16 21 4 9 13

编程： 生成二叉树排序树之后，再中序遍历排序查找结点的完整程序如下： 说明部分为： #include #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(xdata)p=p->lchild; else p=p->rchild; }

if(xdata)q->lchild=s; else q->rchild=s; }

DLR(liuyu *root) /*中序遍历 递归函数*/ {if(root!=NULL)

{if((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf(\ DLR(root->lchild); DLR(root->rchild); } return(0); }

main() /*先生成二叉排序树，再调用中序遍历递归函数进行排序输出*/ {int i,x; i=1;

root=NULL; /*千万别忘了赋初值给root!*/ do{printf(\i++;

scanf(\ /*从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){

6

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; }

p=p+1; return(p); }

法二：

int Get_Sub_Depth(Bitree T,int x)//求二叉树中以值为x的结点为根的子树深度 {

if(T->data==x) {

printf(\找到了值为x的结点,求其深度 exit 1;

7

} } 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 #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) /*如何接入二叉排序树的适当位置*/

8

{q=p;

if(p->data==x){printf(\else if(xdata)p=p->lchild; else p=p->rchild; }

if(xdata)q->lchild=s; else q->rchild=s; }

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; }

p=p+1; return(p); }

void main() /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/ {int i,x; i=1;

root=NULL; /*千万别忘了赋初值给root!*/ do{printf(\i++;

scanf(\ /*从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){

printf(\ else insert_data(x);} /*调用插入数据元素的函数*/ while(x!=-9999); return;} 执行结果：

9

3. 【严题集6.47④】编写按层次顺序（同一层自左至右）遍历二叉树的算法。 或：按层次输出二叉树中所有结点；

解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。

技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，……以此产生了按层次输出的效果。 level(liuyu*T)

/* liuyu *T,*p,*q[100]; 假设max已知*/ {int f,r;

f=0; r=0; /*置空队*/ r=(r+1)%max;

q[r]=T; /*根结点进队*/ while(f!=r) /*队列不空*/ {f=(f+1%max);

p=q[f]; /*出队*/

printf(\ /*打印根结点*/

if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空，则左子树进队*/ if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空，则右子树进队*/ }

return(0); }

法二：

void LayerOrder(Bitree T)//层序遍历二叉树 {

InitQueue(Q); //建立工作队列

EnQueue(Q,T);

while(!QueueEmpty(Q)) {

DeQueue(Q,p); visit(p);

if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }

}//LayerOrder

可以用前面的函数建树，然后调用这个函数来输出。

完整程序如下（已上机通过） #include #include #define max 50

typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test; liuyu *root,*p,*q[max];

10