数据结构二叉树的遍历

数据结构实验报告班级：学号：姓名：计算机科学与技术学院ABCDGEF题目：二叉树的遍历一、设计内容从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历。然后将遍历结果输出。先序、中序、后序遍历要求采用递归和非递归实现。对于如右图所示的二叉树，其扩展的先序遍历序列为：ABD.G..CE..F..（其中小圆点表示空子树）当输入扩展的先序遍历序列：ABD.G..CE..F..输出应该为：层次遍历：ABCDEFG先序遍历：ABDGCEF中序遍历：DGBAECF后续遍历：GDBEFCA二、设计目的1.达到熟练掌握C++语言的基本知识和技能；2.能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。三、系统分析与设计（确定程序功能模块）1.定义二叉链表存储结构2.以先序遍历建立二叉链表，CreateBiTree(BiTree*bt)3.实现先序遍历二叉树的递归算法，PreOrder(BiTreebt)4实现中序遍历二叉树的递归算法，InOrder(BiTreebt)5.实现后序遍历二叉树的递归算法，PostOrder(BiTreebt)6.实现先序遍历二叉树的非递归算法，NRPreOrder(BiTreebt)7.实现中序遍历二叉树的非递归算法，NRInOrder(BiTreebt)8.实现后序遍历二叉树的非递归算法，NRPostOrder(BiTreebt)9.实现层次遍历二叉树的递归算法，LevelOrder(BiTreebt)10.调用各个函数输出遍历结果四、源程序代码#includeiostream.h#includestdio.h#includemalloc.htypedefstructNode{/*声明二叉树二叉链表节点的结构！*/chardata;structNode*lchild;structNode*rchild;}BiTNode,*BiTree;typedefstruct{/*定义结构体（将栈中元素的数据类型定义为指针和标志flag合并的结构体类型）*/BiTreelink;intflag;}stacktype;//*************函数声明**************//voidVisite(chara);voidCreateBiTree(BiTree*bt);voidPreOrder(BiTreebt);voidInOrder(BiTreebt);voidPostOrder(BiTreebt);voidNRPreOrder(BiTreebt);voidNRInOrder(BiTreebt);voidNRPostOrder(BiTreebt);voidLevelOrder(BiTreebt);//***********定义函数（访问节点的数据域）**********//voidVisite(chara){couta;}//***********层次遍历二叉树**********//voidLevelOrder(BiTreebt){BiTreequeue[50];intfront,rear;if(bt==NULL)return;front=-1;rear=0;queue[rear]=bt;while(front!=rear){front++;Visite(queue[front]-data);if(queue[front]-lchild!=NULL){rear++;queue[rear]=queue[front]-lchild;}if(queue[front]-rchild!=NULL){rear++;queue[rear]=queue[front]-rchild;}}}//**********先序遍历建立二叉树***********//voidCreateBiTree(BiTree*bt){charch;ch=getchar();if(ch=='.')*bt=NULL;else{*bt=(BiTree)malloc(sizeof(BiTNode));(*bt)-data=ch;CreateBiTree(&((*bt)-lchild));CreateBiTree(&((*bt)-rchild));}}//**********递归先序遍历二叉树bt***********//voidPreOrder(BiTreebt){if(bt==NULL)return;coutbt-data;PreOrder(bt-lchild);PreOrder(bt-rchild);}//**********递归中序遍历二叉树bt***********//voidInOrder(BiTreebt){if(bt==NULL)return;InOrder(bt-lchild);coutbt-data;InOrder(bt-rchild);}//**********递归后序遍历二叉树bt***********//voidPostOrder(BiTreebt){if(bt==NULL)return;PostOrder(bt-lchild);PostOrder(bt-rchild);coutbt-data;}//**********非递归先序遍历二叉树bt*********//voidNRPreOrder(BiTreebt){BiTreestack[20],p;inttop;if(bt==NULL)return;top=0;p=bt;while(!(p==NULL&&top==0)){while(p!=NULL){Visite(p-data);if(top20-1){stack[top]=p;top++;}else{cout溢出！;return;}p=p-lchild;}if(top=0)return;else{top--;p=stack[top];p=p-rchild;}}}//**********非递归中序遍历二叉树bt***********//voidNRInOrder(BiTreebt){BiTreestack[20],p;inttop;if(bt==NULL)return;top=0;p=bt;while(!(p==NULL&&top==0)){while(p!=NULL){if(top20-1){stack[top]=p;top++;}else{cout溢出！;return;}p=p-lchild;}if(top=0)return;else{top--;p=stack[top];Visite(p-data);p=p-rchild;}}}//*********非递归后序遍历二叉树bt************//voidNRPostOrder(BiTreebt){stacktypestack[50];BiTreep;inttop,sign;if(bt==NULL)return;top=-1;p=bt;while(!(p==NULL&&top==-1)){if(p!=NULL){top++;stack[top].link=p;stack[top].flag=1;p=p-lchild;}else{p=stack[top].link;sign=stack[top].flag;top--;if(sign==1){top++;stack[top].link=p;stack[top].flag=2;p=p-rchild;}else{Visite(p-data);p=NULL;}}}}//********主函数***********//voidmain(){cout请输入序列：endl;BiTreebt;CreateBiTree(&bt);cout\n层次遍历:;LevelOrder(bt);cout\n\n先序、中序、后序遍历的递归实现:;cout\n先序遍历:;PreOrder(bt);cout\n中序遍历:;InOrder(bt);cout\n后序遍历:;PostOrder(bt);cout\n\n先序、中序、后序遍历的非递归实现:;cout\n先序遍历:;NRPreOrder(bt);cout\n中序遍历:;NRInOrder(bt);cout\n后序遍历:;NRPostOrder(bt);cout\n\n;}五、测试结果及功能说明六、设计体会1.通过这次试验，使我更加牢固得掌握了二叉树的建立和各种方式的遍历，感到数的建立，递归二叉树的先序、中序、后序遍历都很简单，非递归先序、中序、后序遍历用到了数组和栈，层次遍历用到了队列，代号为复杂点。2.我意识到在编程过程中，养成良好的编程习惯很重要，否则出错后要浪费大量的时间在找错上，这样既降低了编程的效率，也不利于自己在编程方面的发展。