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

1、数据结构与算法 实验报告实验名称：二叉树各种基本运算与遍历算法班 级：10 软工转本 1姓 名：季佳宾学 号：10130605类 型：综合实验地点：鹤琴 404日 期：2012.11.15、实验目的：1. 理解二叉树的概念及其基本运算算法（这些算法包括二叉树的创建、节点访问、求二叉 树的深度以及二叉树的先根遍历、中根遍历、后根遍历算法）2. 用 c 语言实现二叉树的基本运算算法和遍历算法。3. 调试程序，编译运行并用数据测试程序4. 熟悉 c 语言编程、实验环境：1. PC机一台（带有 VS 6.0 软件） 三、实验内容和要求：1、用 c 语言实现二叉树的基本运算算法 （包括二叉树的创建、 节

2、点访问、 求二叉树的深度）2、用 c 语言实现二叉树的三种遍历算法（先根遍历、中根遍历、后根遍历），其中中根遍历 算法用递归和非递归两种方式实现，加深理解栈在非递归实现中的应用；3、调试程序，编译运行并用数据测试程序四、实验步骤： （对实验步骤的说明应该能够保证根据该说明即可重复完整的实验内容，得到正确结果。 ） 1、 对实现二叉树的基本运算算法以及遍历算法做分析，绘制算法流程图1） 设计二叉树的节点表示方法2）设计和实现相关算法函数2、在 VS6.0 环境下编译实现代码1）编辑源程序，达到调试编译运行的目的2）利用数据进行测试验证五、实验结果与分析（ 含程序、数据记录及分析和实验总结等 ）：

3、实验 7.1 实现二叉树各种基本运算的算法，代码如下所示：#include #include #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)cas

4、e (: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)case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;BTNode *FindNode(BTNode *b,ElemType x)BTNode *p;if(b=NULL)return NULL

5、;else if(b-data=x)return b;elsep=FindNode(b-lchild,x);if(p!=NULL)return p;elsereturn FindNode(b-rchild,x);BTNode *LchildNode(BTNode *p)return p-lchild;BTNode *RchildNode(BTNode *p)return p-rchild;int BTNodeDepth(BTNode *b)int lchilddep,rchilddep;if(b=NULL)return(0);else lchilddep=BTNodeDepth(b-lchil

6、d); rchilddep=BTNodeDepth(b-rchild);return (lchilddeprchilddep)?(lchilddep+1):(rchilddep+1); 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();int BTWidth(BTNode *b)struct

7、int lno;BTNode *p;QuMaxSize;int front,rear;int lnum,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=

8、1;i=1; while(i=rear)n=0;while(imax) max=n;return max;elsereturn 0;int Nodes(BTNode*b)int num1,num2; if(b=NULL) return 0;else if(b-lchild=NULL&b-rchild=NULL)return 1;else num1=Nodes(b-lchild); num2=Nodes(b-rchild); return(num1+num2+1);int LeafNodes(BTNode*b)int num1,num2; if(b=NULL) return 0;else if(

9、b-lchild=NULL&b-rchild=NULL)return 1;else num1=LeafNodes(b-lchild); num2=LeafNodes(b-rchild); return(num1+num2);void main()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=LchildN

10、ode(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); p

11、rintf(n);word 教育资料实验结果：实验 7.2 实现二叉树各种遍历算法，代码如下所示：#include stdio.h #include malloc.h #define MaxSize 100 typedef char ElemType; typedef struct node ElemType 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 c

12、h ;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)case 1:Sttop-lchild=p;break;case 2:Sttop-rchild=p;break;j+;ch=strj;void DispBTNode(BTNode

13、*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

14、 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)BTNod

15、e *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)B

16、TNode *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-;v

17、oid 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 PostOrder

18、1(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-

19、;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;Qurear=b-rc