实验四--二叉树的操作

实验四二叉树的操作学号：0700710319姓名：梁浩然实验日期：2009年5月13日一、实验目的（1）掌握二叉树链表的结构和二叉树的建立过程。（2）掌握队列的先进先出的运算原则在解决实际问题中的应用。（3）进一步掌握指针变量、指针数组、动态变量的含义。（4）掌握递归程序设计的特点和编程方法。二、实验要求（1）熟练掌握二叉链表的存储结构。（2）熟练掌握循环队列的基本操作。（3）理解所给出的算法，掌握循环队列在实际中的应用。（4）加深对递归算法的理解。（5）将上机程序调试通过，并能独立完成一至两个拓展题目。三、实验内容已知以二叉链表作存储结构，试编写按层次遍历二叉树的算法。（所谓层次遍历，是指从二叉树的根结点开始从上到下逐层遍历二叉树，在同一层次中从左到右依次访问各个节点。）调试程序并对相应的输出作出分析；修改输入数据，预期输出并验证输出的结果。加深对算法的理解。四、实验方法本算法要采用一个循环队列que，先将二叉树根结点入队列，然后退队列，输出该结点；若它有左子树，便将左子树根结点入队列；若它有右子树，便将右子树根结点入队列，直到队列空为止。因为队列的特点是先进先出，从而达到按层次顺序遍历二叉的目的。所给程序修改如下：#includestdio.h#includemalloc.h/*包含动态分配内存函数*/#defineTRUE1#defineFALSE0#defineM100#defineNULL0typedefstructnode/*二叉链表结点结构*/{intdata;/*数据域*/structnode*lchild,*rchild;/*左、右孩子域*/}bitree;bitree*que[M];/*定义一个指针数组，说明队列中的元素类型为bitree指针类型*/intfront=0,rear=0;/*初始化循环队列*/bitree*creat()/*建立二叉树的递归算法*/{bitree*t;intx;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();}returnt;}voidinorder(bitree*t)/*中序遍历二叉树的递归算法*/{if(t!=NULL){inorder(t-lchild);printf(%4d,t-data);inorder(t-rchild);}}voidenqueue(bitree*t)/*把bitree类型的结点*t入队列*/{if(front!=(rear+1)%M)/*判断队列是否已满*/{rear=(rear+1)%M;que[rear]=t;}}bitree*delqueue(){if(front==rear)/*判断队列不为空*/returnNULL;front=(front+1)%M;return(que[front]);}voidlevorder(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);}}}voidmain()/*主函数*/{bitree*root;printf(\n);root=creat();inorder(root);printf(\n);levorder(root);printf(\n);}运行结果：拓展内容：（1）写出二叉树前序遍历和后序遍历的递归算法，并在主函数中调用它，调试好程序并分析其运行结果。voidpreorder(bitree*t)/*前序遍历二叉树的递归算法*/{if(t!=NULL){printf(%4d,t-data);preorder(t-lchild);preorder(t-rchild);}}voidpostorder(bitree*t)/*前序遍历二叉树的递归算法*/{if(t!=NULL){postorder(t-lchild);postorder(t-rchild);printf(%4d,t-data);}}（3）写出二叉树三种遍历的非递归算法，并在主函数中调用它，调试好程序并分析其运行结构。1.先序遍历非递归算法#definemaxsize100typedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidPreOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null||!StackEmpty(s)){while(p!=null)//遍历左子树{visite(p-data);push(s,p);p=p-lchild;}//endwhileif(!StackEmpty(s))//通过下一次循环中的内嵌while实现右子树遍历{p=pop(s);p=p-rchild;}//endif}//endwhile}//PreOrder2.中序遍历非递归算法#definemaxsize100typedefstruct{BitreeElem[maxsize];inttop;}SqStack;voidInOrderUnrec(Bitreet){SqStacks;StackInit(s);p=t;while(p!=null||!StackEmpty(s)){while(p!=null)//遍历左子树{push(s,p);p=p-lchild;}//endwhileif(!StackEmpty(s)){p=pop(s);visite(p-data);//访问根结点p=p-rchild;//通过下一次循环实现右子树遍历}//endif}//endwhile}//InOrder3.后序遍历非递归算法#definemaxsize100typedefenum{L,R}tagtype;typedefstruct{Bitreeptr;tagtypetag;}stacknode;typedefstruct{stacknodeElem[maxsize];inttop;}SqStack;voidPostOrderUnrec(Bitreet){SqStacks;stacknodex;StackInit(s);p=t;do{while(p!=null)//遍历左子树{x.ptr=p;x.tag=L;//标记为左子树push(s,x);p=p-lchild;}while(!StackEmpty(s)&&s.Elem[s.top].tag==R){x=pop(s);p=x.ptr;visite(p-data);//tag为R，表示右子树访问完毕，故访问根结点}if(!StackEmpty(s)){s.Elem[s.top].tag=R;//遍历右子树p=s.Elem[s.top].ptr-rchild;}}while(!StackEmpty(s));}//PostOrder五、实验小结（1）通过本次实验掌握了二叉树链表的结构和二叉树的建立过程。（2）进一步理解了队列的先进先出的运算原则在解决实际问题中的应用。（3）通过理解所给出的算法，掌握循环队列在实际中的应用，并且加深了对递归算法的理解。