实验四 二叉树的操作.docVIP

实验四 二叉树的操作 学号：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