实验四 二叉树的操作.doc
文本预览下载声明
实验四 二叉树的操作
学号：0700710319 姓名：梁浩然 实验日期：2009年5月13日
实验目的
掌握二叉树链表的结构和二叉树的建立过程。
掌握队列的先进先出的运算原则在解决实际问题中的应用。
进一步掌握指针变量、指针数组、动态变量的含义。
掌握递归程序设计的特点和编程方法。
二、实验要求
熟练掌握二叉链表的存储结构。
熟练掌握循环队列的基本操作。
理解所给出的算法，掌握循环队列在实际中的应用。
加深对递归算法的理解。
将上机程序调试通过，并能独立完成一至两个拓展题目。
三、实验内容
已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。
四、实验方法
本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。
所给程序修改如下：
#include stdio.h
#include malloc.h /*包含动态分配内存函数*/
#define TRUE 1
#define FALSE 0
#define M 100
#define NULL 0
typedef struct node /*二叉链表结点结构*/
{ int data; /*数据域*/
struct node *lchild,*rchild;/*左、右孩子域*/
} bitree;
bitree *que[M]; /*定义一个指针数组，说明队列中的元素类型为bitree指针类型*/
int front=0,rear=0; /*初始化循环队列*/
bitree *creat() /*建立二叉树的递归算法*/
{ bitree *t;
int x;
scanf(%d,x);
if(x==0) t=NULL; /*以x=0表示输入结束*/
else{
t=(bitree *)malloc(sizeof(bitree)); /*动态生成结点t,分别给结点t的数据域、左右孩子域赋值,给左右孩子域赋值时用到了递归的思想。*/
t-data=x;
t-lchild=creat();
t-rchild=creat();
}
return t;
}
void inorder(bitree *t) /*中序遍历二叉树的递归算法*/
{if(t!=NULL)
{inorder(t-lchild);
printf(%4d,t-data);
inorder(t-rchild);
}
}
void enqueue(bitree *t) /*把bitree类型的结点*t入队列*/
{if(front!=(rear+1)%M) /*判断队列是否已满*/
{rear=(rear+1)%M;
que[rear]=t;
}
}
bitree *delqueue()
{ if(front==rear) /*判断队列不为空*/
return NULL;
front=(front+1)%M;
return (que[front]);
}
void levorder(bitree *t) /*层次遍历二叉树的算法*/
{bitree *p;
if(t!=NULL)
{enqueue(t); /*根结点入队*/
while(front!=rear) /*当当前队列不为空时*/
{p=delqueue(); /*输出对头元素，并把其左右孩子入队。此过程一直递归，直到队列为空*/
printf(%4d,p-data);
if(p-lchild!=NULL)
enqueue(p-lchild);
if(p-rchild!=NULL)
enqueue(p-rchild);}
}
}
void main() /*主函数*/
{ bitree *root;
printf(\n);
root=creat();
inorder(root);
printf(\n);
levorder(root);
printf(\n);
}
运行结果：
拓展内容：
（1）写出二叉树前序遍历和后序遍历的递归算法，并在主函数中调用它，调试好程序并分析其运行结果。
void preorder(bitr
显示全部