数据结构习题集与实验指导

.

3.给定二叉树的两种遍历序列，分别是：

前序遍历序列：D，A，C，E，B，H，F，G，I； 中序遍历序列：D，C，B，E，H，A，G，I，F， 试画出二叉树B，并简述由任意二叉树B的前序遍历序列和中序遍历序列求二叉树B的思想方法。 解：方法是：由前序先确定root，由中序可确定root的左、右子树。然后由其左子树的元素集合和右子树的集合对应前序遍历序列中的元素集合，可继续确定root的左右孩子。将他们分别作为新的root，不断递归，则所有元素都将被唯一确定，问题得解。 4.给定如图所示二叉树T，请画出与其对应的中序线索二叉树。 解：要遵循中序遍历的轨迹来画出每个前驱和后继。 28 中序遍历序列：55 40 25 60 28 08 33 54 25 33 然后画出相应的中序线索二叉树。 40 60 08 54 55

五、阅读分析题

1.试写出如图所示的二叉树分别按先序、中序、后序遍历时得到的结点序列。

答：DLR：A B D F J G K C E H I L M LDR: B F J D G K A C H E L I M LRD：J F K G D B H L M I E C A

2.把如图所示的树转化成二叉树。

答：注意全部兄弟之间都要连线（包括度为2的兄弟）,并注意原有连线结点一律归入左子树，新添连线结点一律归入右子树。 A B

E C

K F H D L G I M J

4.画出和下列二叉树相应的森林。

.

.

答：注意根右边的子树肯定是森林， 而孩子结点的右子树均为兄弟。

六、算法设计题

1.写出求二叉树深度的算法，先定义二叉树的抽象数据类型。

或编写递归算法，求二叉树中以元素值为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; } } 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

2.编写按层次顺序（同一层自左至右）遍历二叉树的算法。 或：按层次输出二叉树中所有结点；

解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法，用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];

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

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

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

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

.