(已处理)内蒙古科技大学课程设计-二叉树遍历及应用

1、遍历二叉树内蒙古科技大学数 据 结 构课程设计题 目二叉树遍历及应用学 号1376807435姓 名亢斌指导教师王丽颖日 期2015年6月30日目 录一、问题描述1二、需求分析12.1主功能模块12.2创建树模块12.3遍历树模块1三、概要设计23.1主界面设计思想流程图23.2. 创建二叉树23.2.1二叉树创建的思想23.2.2二叉树创建的算法流程图23.3.先序递归遍历33.3.1先序递归遍历思想33.3.2先序递归遍历的算法流程图33.4.中序递归遍历33.4.1中序递归遍历思想33.4.2中序递归遍历的算法流程图43.5.后序递归遍历43.5.1后序递归遍历思想43.5.2后序递归遍

2、历的算法流程图53.6.先序非递归遍历53.6.1先序非递归遍历思想53.6.2先序非递归遍历的算法流程图63.7.中序非递归遍历63.7.1中序非递归遍历思想63.7.2中序非递归遍历的算法流程图73.8.后序非递归遍历73.8.1后序非递归遍历思想73.8.2后序非递归遍历的算法流程图83.9.层序非递归遍历83.9.1层序非递归遍历思想83.9.2层序非递归遍历的算法流程图9四、详细设计104.1界面设计104.2.详细代码分析114.2.1主模块114.2.2创建树模块124.2.3遍历树模块13五、调试分析135.1.调试结果135.1.1实验数据135.1.2创建树界面145.1.

3、3输出结果界面14六、 总结附录：程序代码一、 问题描述建立二叉树, 层序、先序、中序、后序遍历.(用递归或非递归的方法都可以)要求能够输入树的各个结点, 并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数. 二、 需求分析在现实世界层次化的数据模型中, 数据与数据之间的关系纷繁复杂. 其中很多关系无法使用简单的线性结构表示清楚, 比如祖先与后代的关系、整体与部分的关系等. 于是人们借鉴自然界中树的形象创造了一种强大的非线性结构树. 树形结构的具体形式有很多种, 其中最常用的就是

4、二叉树. 而二叉树的多层次遍历遍历则是二叉树的重要内容. 本程序用Microsoft Visual C+ 6.0编写, 可以实现对二叉树的创建、采用递归和非递归等两种方式先序、中序、后序进行遍历. 2.1主功能模块通过合理的界面设计, 根据提示信息, 使用者可以方便快捷地运行本程序来完成创建、遍历二叉树等操作. 界面美观, 人性化, 程序智能, 安全性高. 2.2创建树模块当进入程序运行界面后, 根据提示输入需要建立的二叉树, 按照先序次序输入各个结点的值, 完成二叉树的建立. 2.3遍历树模块实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归

5、遍历、层序非递归遍历等方式的遍历操作, 并输出各遍历序列. 三、 概要设计3.1主界面设计思想流程图3.2. 创建二叉树3.2.1二叉树创建的思想(1)定义二叉树结点值的类型为字符型. (2)结点个数不超过10个. (3)按先序次序输入, 构造二叉链表表示的二叉树T, 空格表示空树. 相关函数如下: void CreateBiTree(BiTree &T)3.2.2二叉树创建的算法流程图开始创建二叉树结束3.3.先序递归遍历3.3.1先序递归遍历思想若二叉树为空, 则空操作；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树. 相关函数如下: void PreOrderT

6、raverse(BiTree T)3.3.2先序递归遍历的算法流程图开始判断结点是否空访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历右子树YN3.4.中序递归遍历3.4.1中序递归遍历思想若二叉树为空, 则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)中序遍历右子树. 相关函数如下: void InOrderTraverse(BiTree T)3.4.2中序递归遍历的算法流程图开始判断结点是否空按中根遍历方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN3.5.后序递归遍历3.5.1后序递归遍历思想若二叉树为空, 则空操作；否则(1)后序遍历左子树；(2)后序遍历右

7、子树；(3)访问根结点. 相关函数如下: void PostOrderTraverse(BiTree T)3.5.2后序递归遍历的算法流程图开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN3.6.先序非递归遍历3.6.1先序非递归遍历思想(1)访问结点的数据域；(2)指针指向p的左孩子结点；(3)从栈中弹出栈顶元素；(4)指针指向p的右孩子结点. 相关函数如下: void NRPreOrder(BiTree bt)3.6.2先序非递归遍历的算法流程图开始申请一个STL栈stack<*> s判断结点是否空输出结点值p->datas.push(

8、p)结点的值变为它的左孩子判断结点是否空p=s.pop()p=p->rchild结束判断栈或结点是否空NYNYN3.7.中序非递归遍历3.7.1中序非递归遍历思想(1)指针指向p的左孩子结点；(2)从栈中弹出栈顶元素；(3)访问结点的数据域；(4)指针指向p的右孩子结点. 相关函数如下: void NRInOrder(BiTree bt)3.7.2中序非递归遍历的算法流程图开始申请一个STL栈stack<*> s判断结点是否空s.push(p)结点的值变为它的左孩子判断结点是否空输出结点值p->datap=s.pop()p=p->rchild结束判断栈或结点是否空

9、NYYNN3.8.后序非递归遍历3.8.1后序非递归遍历思想若二叉树为空, 则空操作；否则引入栈和标记模拟递归工作栈, 初始时栈为空. 相关函数如下: void NRPostOrder(BiTree bt);3.8.2后序非递归遍历的算法流程图开始申请一个STL栈stack<*> s;用一个bool变量flag标记是否访问flag=0 s.push(p)p=p->lchild top+判断标志flag是否为1输出结点的数据p->datap = s.pop()p= p->rchild结束NYYNNYYN判断结点是否空判断栈或结点是否空判断结点是否空3.9.层序非递归

10、遍历3.9.1层序非递归遍历思想(1)访问该元素所指结点. (2)若该元素所指结点的左右孩子结点非空, 则该元素所指结点的左孩子指针和右孩子指针顺序入队. 相关函数如下: void LevelOrderTraverse(BiTree T)3.9.2层序非递归遍历的算法流程图开始申请一个STL队列queue<*> q结束N判断结点是否空Y判断左结点是否空q.push(p->rchild)q.push(p->lchild)判断右结点是否空q.push(root);判断队列是否为空p=q.front()；输出结点值p->data; q.pop()YYNNYN四、 详细设

11、计4.1界面设计图4-1 系统运行主界面图4-2 创建二叉树界面图4-3 二叉树递归遍历界面4.2.详细代码分析4.2.1主模块本模块定义了系统运行主界面的相关内容和相关操作函数, 源代码如下: void main() BiTree T; T=NULL; int select; /cout<<"请按先序次序输入各结点的值, 以空格表示空树(输入时可连续输入):"<<endl;/ CreateBiTree(T); while(1) cout<<"nn请选择要执行的操作:n" cout<<"1.创建二

12、叉树n" cout<<"2.二叉树的递归遍历算法（前、中、后）n" cout<<"3.二叉树的层次遍历算法n"cout<<"4.二叉树的非递归遍历算法（前、中、后）n" cout<<"0.退出n" cin>>select; switch(select) case 0:return; case 1: cout<<"请按先序次序输入各结点的值, 以空格表示空树(输入时可连续输入):"<<endl; Crea

13、teBiTree(T); break; case 2: if(!T) cout<<"未建立树, 请先建树！" else cout<<"n先序遍历:n" PreOrderTraverse(T); cout<<"n中序遍历:n" InOrderTraverse(T); cout<<"n后序遍历:n" PostOrderTraverse(T); break; case 3: cout<<"n层序遍历:n" LevelOrderTraverse

14、(T); break; case 4: if(!T) cout<<"未建立树, 请先建树！" else cout<<"n先序遍历:n" NRPreOrder(T); cout<<"n中序遍历:n" NRInOrder(T); cout<<"n后序遍历:n" NRPostOrder(T); break; default: cout<<"请确认选择项:n" /end switch /end while4.2.2创建树模块源代码如下: voi

15、d CreateBiTree(BiTree &T)/按先序次序输入, 构造二叉链表表示的二叉树T, 空格表示空树/ if(T) return; char ch; ch=getchar(); /不能用cin来输入, 在cin中不能识别空格. if(ch=' ') T=NULL; else if(!(T=(BTNode *)malloc(sizeof(BTNode) cout<<"malloc fail!" T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild

16、); 4.2.3遍历树模块本模块包括了各种遍历二叉树的函数, 源代码如下: void PreOrderTraverse(BiTree T) /二叉树的先序遍历(递归)成员函数声明void InOrderTraverse(BiTree T) /二叉树的中序遍历(递归)成员函数声明void PostOrderTraverse(BiTree T) /二叉树的后序遍历(递归)成员函数声明void LevelOrderTraverse(BiTree T) / 二叉树的层序遍历(非递归)成员函数声明void NRPreOrder(BiTree bt) / 二叉树的先序遍历(非递归)成员函数声明void N

17、RInOrder(BiTree bt) /二叉树的中序遍历(非递归)成员函数声明void NRPostOrder(BiTree bt) /二叉树的后序遍历(非递归)成员函数声明五、 调试分析5.1.调试结果5.1.1实验数据ABCDEFHG这棵树是随机画的, 由数据结构知识, 按照先序次序输入各个节点的值为: ABD#CEG#F#H#(此处#代表空格). 在程序中输入这些节点, 创建树, 如下图: 5.1.2创建树界面图5-1 创建树界面5.1.3输出结果界面输入2, 输出该二叉树递归遍历算法的遍历结果, 结果如下: 输入3, 输出该二叉树层序遍历算法的遍历结果, 结果如下: 输入4, 输出该

18、二叉树非递归遍历算法的遍历结果, 结果如下: 六、总结感谢老师的指导！同时感谢同学的帮助。附录：程序代码#include "iostream"#include "stdlib.h"#include "stdio.h"using namespace std;typedef char ElemType;/定义二叉树结点值的类型为字符型const int MaxLength=10;/结点个数不超过10个typedef struct BTNode ElemType data; struct BTNode *lchild,*rchild; BT

19、Node,* BiTree;void CreateBiTree(BiTree &T) /按先序次序输入，构造二叉链表表示的二叉树T，空格表示空树 char ch; ch=getchar(); /不能用cin来输入，在cin中不能识别空格。 if(ch=' ') T=NULL; else if(!(T=(BTNode *)malloc(sizeof(BTNode) cout<<"malloc fail!" T->data=ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild

20、); void PreOrderTraverse(BiTree T) /先序遍历 if(T) cout<<T->data<<' ' PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); void InOrderTraverse(BiTree T) /中序遍历 if(T) InOrderTraverse(T->lchild); cout<<T->data<<' ' InOrderTraverse(T->rchild);

21、void PostOrderTraverse(BiTree T) /后序遍历 if(T) PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data<<' ' void LevelOrderTraverse(BiTree T) /层序遍历 BiTree QMaxLength; int front=0,rear=0; BiTree p; if(T) /根结点入队 Qrear=T; rear=(rear+1)%MaxLength; while(front

22、!=rear) p=Qfront; /队头元素出队 front=(front+1)%MaxLength; cout<<p->data<<' ' if(p->lchild) /左孩子不为空，入队 Qrear=p->lchild; rear=(rear+1)%MaxLength; if(p->rchild) /右孩子不为空，入队 Qrear=p->rchild; rear=(rear+1)%MaxLength; /非递归的先序遍历算法void NRPreOrder(BiTree bt) BiTree stackMaxLength

23、,p; int top; if (bt!=NULL) top=0; p=bt; while(p!=NULL|top>0) while(p!=NULL) cout<<p->data; stacktop=p; top+; p=p->lchild; if (top>0) top-; p=stacktop; p=p->rchild; /非递归的中序遍历算法void NRInOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0; p=bt; while(p!=NULL|top

24、>0) while(p!=NULL) stacktop=p; top+; p=p->lchild; if (top>0) top-; p=stacktop; cout<<p->data; p=p->rchild; /非递归的后序遍历算法typedef struct BiTree ptr; int tag; stacknode;void NRPostOrder(BiTree bt) stacknode sMaxLength,x; BiTree p=bt; int top; if(bt!=NULL) top=0; p=bt; do while (p!=NU

25、LL) /遍历左子树 stop.ptr = p; stop.tag = 1; /标记为左子树 top+; p=p->lchild; while (top>0 && stop-1.tag=2) x = s-top; p = x.ptr; cout<<p->data; /tag为R，表示右子树访问完毕，故访问根结点 if (top>0) stop-1.tag =2; /遍历右子树 p=stop-1.ptr->rchild; while (top>0); int main() BiTree T; T=NULL; int select; while(1) cout<<"nn请选择要执行的操作:n" cout<<"1.创建二叉树n" cout<