二叉树各种基本运算与遍历算法.doc

数据结构与算法 实验报告实验名称：二叉树各种基本运算与遍历算法班 级：10软工转本1姓 名：季佳宾学 号：10130605类 型：综合实验地点：鹤琴404日 期：2012.11.15一、实验目的：1. 理解二叉树的概念及其基本运算算法（这些算法包括二叉树的创建、节点访问、求二叉树的深度以及二叉树的先根遍历、中根遍历、后根遍历算法）2. 用c语言实现二叉树的基本运算算法和遍历算法。3. 调试程序，编译运行并用数据测试程序4. 熟悉c语言编程二、实验环境：1. PC机一台（带有VS 6.0软件）三、实验内容和要求：1、用c语言实现二叉树的基本运算算法（包括二叉树的创建、节点访问、求二叉树的深度）；2、用c语言实现二叉树的三种遍历算法（先根遍历、中根遍历、后根遍历），其中中根遍历算法用递归和非递归两种方式实现，加深理解栈在非递归实现中的应用；3、调试程序，编译运行并用数据测试程序四、实验步骤：（对实验步骤的说明应该能够保证根据该说明即可重复完整的实验内容，得到正确结果。）1、 对实现二叉树的基本运算算法以及遍历算法做分析，绘制算法流程图1） 设计二叉树的节点表示方法2）设计和实现相关算法函数2、在VS6.0环境下编译实现代码1）编辑源程序，达到调试编译运行的目的2）利用数据进行测试验证五、实验结果与分析（含程序、数据记录及分析和实验总结等）：实验7.1实现二叉树各种基本运算的算法，代码如下所示：#include#include#defineMaxSize100typedefcharElemType;typedefstructnodeElemTypedata;structnode*lchild;structnode*rchild;BTNode;voidCreateBTNode(BTNode*&b,char*str)BTNode*StMaxSize,*p=NULL;inttop=-1,k,j=0;charch;b=NULL;ch=strj;while(ch!=0)switch(ch)case(:top+;Sttop=p;k=1;break;case):top-;break;case,:k=2;break;default:p=(BTNode*)malloc(sizeof(BTNode);p-data=ch;p-lchild=p-rchild=NULL;if(b=NULL)b=p;elseswitch(k)case1:Sttop-lchild=p;break;case2:Sttop-rchild=p;break;j+;ch=strj;BTNode*FindNode(BTNode*b,ElemTypex)BTNode*p;if(b=NULL)returnNULL;elseif(b-data=x)returnb;elsep=FindNode(b-lchild,x);if(p!=NULL)returnp;elsereturnFindNode(b-rchild,x);BTNode*LchildNode(BTNode*p)returnp-lchild;BTNode*RchildNode(BTNode*p)returnp-rchild;intBTNodeDepth(BTNode*b)intlchilddep,rchilddep;if(b=NULL)return(0);elselchilddep=BTNodeDepth(b-lchild);rchilddep=BTNodeDepth(b-rchild);return(lchilddeprchilddep)?(lchilddep+1):(rchilddep+1);voidDispBTNode(BTNode*b)if(b!=NULL)printf(%c,b-data);if(b-lchild!=NULL|b-rchild!=NULL)printf();DispBTNode(b-lchild);if(b-rchild!=NULL)printf(,);DispBTNode(b-rchild);printf();intBTWidth(BTNode*b)structintlno;BTNode*p;QuMaxSize;intfront,rear;intlnum,max,i,n;front=rear=0;if(b!=NULL)rear+;Qurear.p=b;Qurear.lno=1;while(rear!=front)front+;b=Qufront.p;lnum=Qufront.lno;if(b-lchild!=NULL)rear+;Qurear.p=b-lchild;Qurear.lno=lnum+1;if(b-rchild!=NULL)rear+;Qurear.p=b-rchild;Qurear.lno=lnum+1;max=0;lnum=1;i=1;while(i=rear)n=0;while(imax)max=n;returnmax;elsereturn0;intNodes(BTNode*b)intnum1,num2;if(b=NULL)return0;elseif(b-lchild=NULL&b-rchild=NULL)return1;elsenum1=Nodes(b-lchild);num2=Nodes(b-rchild);return(num1+num2+1);intLeafNodes(BTNode*b)intnum1,num2;if(b=NULL)return0;elseif(b-lchild=NULL&b-rchild=NULL)return1;elsenum1=LeafNodes(b-lchild);num2=LeafNodes(b-rchild);return(num1+num2);voidmain()BTNode*b,*p,*lp,*rp;CreateBTNode(b,A(B(D,E(H(J,K(L,M(,N),C(F,G(,I);printf(n);printf(1)输出二叉树:);DispBTNode(b);printf(n);printf(2)H结点:);p=FindNode(b,H);if(p!=NULL)lp=LchildNode(p);if(lp!=NULL)printf(左孩子为%c,lp-data);elseprintf(无左孩子);rp=RchildNode(p);if(rp!=NULL)printf(右孩子为%c,rp-data);elseprintf(无右孩子);printf(n);printf(3)二叉树b的深度:%dn,BTNodeDepth(b);printf(4)二叉树b的宽度:%dn,BTWidth(b);printf(5)二叉树b的结点个数:%dn,Nodes(b);printf(6)二叉树b的叶子结点个数:%dn,LeafNodes(b);printf(n);实验结果：实验7.2实现二叉树各种遍历算法，代码如下所示：#include stdio.h#include malloc.h#define MaxSize 100typedef char ElemType;typedef struct nodeElemType data;struct node *lchild;struct node *rchild;BTNode;void CreateBTNode(BTNode *&b,char *str)BTNode *StMaxSize,*p=NULL;int top=-1,k,j=0;char ch ;b=NULL;ch=strj;while (ch!=0)switch(ch)case (:top+;Sttop=p;k=1;break;case):top-;break;case ,:k=2;break;default:p=(BTNode *)malloc(sizeof(BTNode);p-data=ch;p-lchild=p-rchild=NULL;if(b=NULL)b=p;else switch(k)case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;void DispBTNode(BTNode *b)if(b!=NULL)printf(%c,b-data);if(b-lchild!=NULL|b-rchild!=NULL)printf();DispBTNode(b-lchild);if(b-rchild!=NULL)printf(,);DispBTNode(b-rchild);printf();void PreOrder(BTNode *b)if(b!=NULL)printf(%c,b-data);PreOrder(b-lchild);PreOrder(b-rchild);void PreOrder1 (BTNode *b)BTNode *p;structBTNode *pt;int tag;StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while(top-1)if(Sttop.tag=1)p=Sttop.pt;top-;if(p!=NULL)top+;Sttop.pt=p-rchild;Sttop.tag=1;top+;Sttop.pt=p-lchild;Sttop.tag=1;top+;Sttop.pt=p;Sttop.tag=0;if(Sttop.tag=0)printf(%c,Sttop.pt-data);top-;void PreOrder2 (BTNode *b)BTNode *StMaxSize,*p;int top=-1;if(b!=NULL)top+;Sttop=b;while (top-1)p=Sttop;top-;printf(%c,p-data);if(p-rchild!=NULL)top+;Sttop=p-rchild;if(p-lchild!=NULL)top+;Sttop=p-lchild;printf(n);void InOrder(BTNode *b)if(b!=NULL)InOrder(b-lchild);printf(%c,b-data);InOrder(b-rchild);void InOrder1(BTNode *b)BTNode *p;structBTNode *pt;int tag;StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while(top-1)if(Sttop.tag=1)p=Sttop.pt;top-;if(p!=NULL)top+;Sttop.pt=p-rchild;Sttop.tag=1;top+;Sttop.pt=p;Sttop.tag=0;top+;Sttop.pt=p-lchild;Sttop.tag=1;if(Sttop.tag=0)printf(%c,Sttop.pt-data);top-;void InOrder2(BTNode *b)BTNode *StMaxSize,*p;int top=-1;if(b!=NULL)p=b;while(top-1|p!=NULL)while(p!=NULL)top+;Sttop=p;p=p-lchild;if(top-1)p=Sttop;top-;printf(%c,p-data);p=p-rchild;printf(n);void PostOrder(BTNode *b)if(b!=NULL)PostOrder(b-lchild);PostOrder(b-rchild);printf(%c,b-data);void PostOrder1(BTNode *b)BTNode *p;structBTNode *pt;int tag;StMaxSize;int top=-1;top+;Sttop.pt=b;Sttop.tag=1;while(top-1)if(Sttop.tag=1)p=Sttop.pt;top-;if(p!=NULL)top+;Sttop.pt=p;Sttop.tag=0;top+;Sttop.pt=p-rchild;Sttop.tag=1;top+;Sttop.pt=p-lchild;Sttop.tag=1;if(Sttop.tag=0)printf(%c,Sttop.pt-data);top-;void PostOrder2(BTNode *b)BTNode*StMaxSize;BTNode*p;int flag,top=-1;if(b!=NULL)dowhile(b!=NULL)top+;Sttop=b;b=b-lchild;p=NULL;flag=1;while(top!=-1&flag)b=Sttop;if(b-rchild=p)printf(%c,b-data);top-;p=b;elseb=b-rchild;flag=0;while(top!=-1);printf(n);void TravLevel(BTNode *b)BTNode*QuMaxSize;int front,rear;front=rear=0;if(b!=NULL)printf(%c,b-data); rear+;Qurear=b;while(rear!=front)front=(front+1)%MaxSize;b=Qufront;if(b-lchild!=NULL)printf(%c,b-lchild-data);rear=(rear+1)%MaxSize;Qurear=b-lchild;if(b-rchild!=NULL)printf(%c,b-rchild-data);rear=(rear+1)%MaxSize;Q