数据结构二叉树的遍历(共10页).doc

《数据结构二叉树的遍历(共10页).doc》由会员分享，可在线阅读，更多相关《数据结构二叉树的遍历(共10页).doc（10页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上数据结构实验报告班级：学号：姓名：计算机科学与技术学院 题目：二叉树的遍历一、设计内容 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历。然后将遍历结果输出。先序、中序、后序遍历要求采用递归和非递归实现。ABCDGEF对于如右图所示的二叉树，其扩展的先序遍历序列为：A B D . G . . C E . . F . .（其中小圆点表示空子树）当输入扩展的先序遍历序列：A B D . G . . C E . . F . . 输出应该为：层次遍历：A B C D E F G 先序遍历：A B D G C E F中序遍历：D G B

2、A E C F 后续遍历：G D B E F C A 二、设计目的1. 达到熟练掌握C+语言的基本知识和技能；2. 能够利用所学的基本知识和技能，解决简单的面向对象程序设计问题。三、系统分析与设计（确定程序功能模块）1.定义二叉链表存储结构2.以先序遍历建立二叉链表，CreateBiTree(BiTree *bt)3.实现先序遍历二叉树的递归算法， PreOrder(BiTree bt)4实现中序遍历二叉树的递归算法， InOrder(BiTree bt)5.实现后序遍历二叉树的递归算法， PostOrder(BiTree bt)6.实现先序遍历二叉树的非递归算法，NRPreOrder (Bi

3、Tree bt)7.实现中序遍历二叉树的非递归算法，NRInOrder (BiTree bt)8.实现后序遍历二叉树的非递归算法，NRPostOrder (BiTree bt)9.实现层次遍历二叉树的递归算法，LevelOrder (BiTree bt)10.调用各个函数输出遍历结果四、源程序代码#include iostream.h#include stdio.h#include malloc.htypedef struct Node/*声明二叉树二叉链表节点的结构！*/ char data; struct Node *lchild; struct Node *rchild;BiTNode,

4、*BiTree;typedef struct /*定义结构体（将栈中元素的数据类型定义为指针和标志flag合并的结构体类型）*/BiTree link;int flag;stacktype;/*函数声明*/void Visite(char a);void CreateBiTree(BiTree *bt);void PreOrder(BiTree bt);void InOrder(BiTree bt);void PostOrder(BiTree bt);void NRPreOrder (BiTree bt);void NRInOrder (BiTree bt);void NRPostOrder

5、(BiTree bt);void LevelOrder (BiTree bt);/*定义函数（访问节点的数据域）*/void Visite(char a) coutadata);if (queuefront-lchild!=NULL)rear+;queuerear=queuefront-lchild;if (queuefront-rchild!=NULL)rear+;queuerear=queuefront-rchild;/*先序遍历建立二叉树*/void CreateBiTree(BiTree *bt)char ch;ch=getchar();if (ch=.) *bt=NULL;else

6、*bt=(BiTree) malloc(sizeof(BiTNode); (*bt)-data=ch; CreateBiTree(&(*bt)-lchild); CreateBiTree(&(*bt)-rchild);/*递归先序遍历二叉树bt*/void PreOrder(BiTree bt) if(bt=NULL) return;coutdatalchild);PreOrder (bt-rchild);/*递归中序遍历二叉树bt*/void InOrder(BiTree bt)if(bt=NULL) return;InOrder (bt-lchild);coutdatarchild);/*

7、递归后序遍历二叉树bt*/void PostOrder(BiTree bt)if(bt=NULL) return;PostOrder (bt-lchild);PostOrder (bt-rchild);coutdatadata);if (top 20-1)stacktop=p;top+;elsecoutlchild;if (toprchild; /*非递归中序遍历二叉树bt*/void NRInOrder (BiTree bt)BiTree stack20,p;int top;if (bt=NULL)return;top=0;p=bt;while(!(p=NULL&top=0)while (p

8、!=NULL)if (top 20-1)stacktop=p;top+;elsecoutlchild;if (topdata);p=p-rchild;/*非递归后序遍历二叉树bt*/void NRPostOrder (BiTree bt)stacktype stack50;BiTree p;int top,sign;if (bt=NULL)return;top=-1;p=bt;while (!(p=NULL&top=-1)if (p!=NULL)top+;stacktop.link=p;stacktop.flag=1;p=p-lchild;elsep=stacktop.link;sign=st

9、acktop.flag;top-;if (sign=1)top+;stacktop.link=p;stacktop.flag=2;p=p-rchild;else Visite (p-data);p=NULL;/*主函数*/void main()cout请输入序列：endl;BiTree bt;CreateBiTree(&bt);coutn层次遍历:;LevelOrder (bt);coutnn先序、中序、后序遍历的递归实现:;coutn先序遍历:;PreOrder(bt);coutn中序遍历:;InOrder(bt);coutn后序遍历:;PostOrder(bt);coutnn先序、中序、后序遍历的非递归实现:;coutn先序遍历:;NRPreOrder (bt);coutn中序遍历:;NRInOrder (bt);coutn后序遍历:;NRPostOrder (bt);coutnn;五、测试结果及功能说明六、设计体会 1.通过这次试验，使我更加牢固得掌握了二叉树的建立和各种方式的遍历，感到数的建立，递归二叉树的先序、中序、后序遍历都很简单，非递归先序、中序、后序遍历用到了数组和栈，层次遍历用到了队列，代号为复杂点。2.我意识到在编程过程中，养成良好的编程习惯很重要，否则出错后要浪费大量的时间在找错上，这样既降低了编程的效率，也不利于自己在编程方面的发展。 专心-专注-专业