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

内蒙古科技大学

《数 据 结 构》

课程设计

题 目 学 号 姓 名 指导教师 日 期

二叉树遍历及应用 **********

亢斌 王丽颖 2015年6月30日

遍历二叉树

目 录

一、 二、

问题描述 ........................................................................................................................... 3 需求分析 ........................................................................................................................... 3 2.1主功能模块 ........................................................................................................................ 3 2.2创建树模块 ........................................................................................................................ 3 2.3遍历树模块 ........................................................................................................................ 3 三、

概要设计 ........................................................................................................................... 4

3.1主界面设计思想流程图 .................................................................................................... 4 3.2. 创建二叉树 ..................................................................................................................... 4

3.2.1二叉树创建的思想 ................................................................................................ 4 3.2.2二叉树创建的算法流程图 .................................................................................... 4 3.3.先序递归遍历 ........................................................................................................... 5 3.3.1先序递归遍历思想 ................................................................................................ 5 3.3.2先序递归遍历的算法流程图 ................................................................................ 5 3.4.中序递归遍历 ........................................................................................................... 5 3.4.1中序递归遍历思想 ................................................................................................ 5 3.4.2中序递归遍历的算法流程图 ................................................................................ 6 3.5.后序递归遍历 ........................................................................................................... 6 3.5.1后序递归遍历思想 ................................................................................................ 6 3.5.2后序递归遍历的算法流程图 ................................................................................ 7 3.6.先序非递归遍历 ....................................................................................................... 7 3.6.1先序非递归遍历思想 ............................................................................................ 7 3.6.2先序非递归遍历的算法流程图 ............................................................................ 8 3.7.中序非递归遍历 ....................................................................................................... 8 3.7.1中序非递归遍历思想 ............................................................................................ 8 3.7.2中序非递归遍历的算法流程图 ............................................................................ 9 3.8.后序非递归遍历 ....................................................................................................... 9 3.8.1后序非递归遍历思想 ............................................................................................ 9 3.8.2后序非递归遍历的算法流程图 .......................................................................... 10 3.9.层序非递归遍历 ..................................................................................................... 10 3.9.1层序非递归遍历思想 .......................................................................................... 10 3.9.2层序非递归遍历的算法流程图 .......................................................................... 11 四、

详细设计 ......................................................................................................................... 12

4.1界面设计 .......................................................................................................................... 12 4.2.详细代码分析 ................................................................................................................. 13

4.2.1主模块 .................................................................................................................. 13 4.2.2创建树模块 .......................................................................................................... 14 4.2.3遍历树模块 .......................................................................................................... 15 五、

调试分析 ......................................................................................................................... 15

5.1.调试结果 ......................................................................................................................... 15

遍历二叉树

5.1.1实验数据 .............................................................................................................. 15 5.1.2创建树界面 .......................................................................................................... 16 5.1.3输出结果界面 ...................................................................................................... 16

六、 总结

附录：程序代码

遍历二叉树

一、 问题描述

建立二叉树, 层序、先序、中序、后序遍历.(用递归或非递归的方法都可以)

要求能够输入树的各个结点, 并能够输出用不同方法遍历的遍历序列；分别建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数.

二、 需求分析

在现实世界层次化的数据模型中, 数据与数据之间的关系纷繁复杂. 其中很多关系无法使用简单的线性结构表示清楚, 比如祖先与后代的关系、整体与部分的关系等. 于是人们借鉴自然界中树的形象创造了一种强大的非线性结构——树. 树形结构的具体形式有很多种, 其中最常用的就是二叉树. 而二叉树的多层次遍历遍历则是二叉树的重要内容.

本程序用Microsoft Visual C++ 6.0编写, 可以实现对二叉树的创建、采用递归和非递归等两种方式先序、中序、后序进行遍历.

2.1主功能模块

通过合理的界面设计, 根据提示信息, 使用者可以方便快捷地运行本程序来完成创建、遍历二叉树等操作. 界面美观, 人性化, 程序智能, 安全性高.

2.2创建树模块

当进入程序运行界面后, 根据提示输入需要建立的二叉树, 按照先序次序输入各个结点的值, 完成二叉树的建立.

2.3遍历树模块

实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历等方式的遍历操作, 并输出各遍历序列.

遍历二叉树

三、 概要设计

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 PreOrderTraverse(BiTree T)

3.3.2先序递归遍历的算法流程图

开始 Y 判断结点是否空 N 访问根结点 按前根遍历方式遍历左子树 按前根遍历方式遍历右子树 结束

3.4.中序递归遍历 3.4.1中序递归遍历思想

若二叉树为空, 则空操作；否则 (1)中序遍历左子树； (2)访问根结点；

(3)中序遍历右子树. 相关函数如下:

遍历二叉树

void InOrderTraverse(BiTree T)

3.4.2中序递归遍历的算法流程图

开始 Y 判断结点是否空 N 按中根遍历方式遍历左子树 访问根结点 按中根遍历方式遍历右子树 结束

3.5.后序递归遍历 3.5.1后序递归遍历思想

若二叉树为空, 则空操作；否则 (1)后序遍历左子树； (2)后序遍历右子树；

(3)访问根结点. 相关函数如下: void PostOrderTraverse(BiTree T)

遍历二叉树

3.5.2后序递归遍历的算法流程图

开始 Y 判断结点是否空 N 按后根遍历方式遍历左子树 按后根遍历方式遍历右子树 访问根结点 结束

3.6.先序非递归遍历 3.6.1先序非递归遍历思想

(1)访问结点的数据域；

(2)指针指向p的左孩子结点； (3)从栈中弹出栈顶元素；

(4)指针指向p的右孩子结点. 相关函数如下: void NRPreOrder(BiTree bt)

遍历二叉树

3.6.2先序非递归遍历的算法流程图

开始 申请一个STL栈stack<*> s N 判断结点是否空 Y 输出结点值p->data s.push(p)结点的值变为它的左孩子 N 判断结点是否空 p=s.pop() p=p->rchild Y 判断栈或结点是否空 N 结束

3.7.中序非递归遍历 3.7.1中序非递归遍历思想

(1)指针指向p的左孩子结点； (2)从栈中弹出栈顶元素； (3)访问结点的数据域；

(4)指针指向p的右孩子结点. 相关函数如下: void NRInOrder(BiTree bt)

遍历二叉树

3.7.2中序非递归遍历的算法流程图

开始 申请一个STL栈stack<*> s N 判断结点是否空 Y s.push(p)结点的值变为它的左孩子 N 判断结点是否空 输出结点值p->data p=s.pop() p=p->rchild Y 判断栈或结点是否空 N 结束

3.8.后序非递归遍历 3.8.1后序非递归遍历思想

若二叉树为空, 则空操作；否则引入栈和标记模拟递归工作栈, 初始时栈为空. 相关函数如下: void NRPostOrder(BiTree bt);

遍历二叉树

3.8.2后序非递归遍历的算法流程图

开始 申请一个STL栈stack<*> s; 用一个bool变量flag标记是否访问 N 判断结点是否空 Y flag=0 s.push(p) p=p->lchild N 判断标志flag是否为1 Y 输出结点的数据p->data N 判断结点是否空 Y p = s.pop() p= p->rchild N 判断栈或结点是否空 Y 结束

3.9.层序非递归遍历 3.9.1层序非递归遍历思想

(1)访问该元素所指结点.

(2)若该元素所指结点的左右孩子结点非空, 则该元素所指结点的左孩子指针和右孩子指针顺序入队.

相关函数如下:

void LevelOrderTraverse(BiTree T)

遍历二叉树

3.9.2层序非递归遍历的算法流程图

开始 申请一个STL队列queue<*> q Y 判断结点是否空 N q.push(root); p=q.front()；输出结点值p->data; Y 判断左结点是否空 N q.push(p->lchild) Y 判断右结点是否空 N q.push(p->rchild) 判断队列是否为空 N Y 结束

遍历二叉树

四、 详细设计

4.1界面设计

图4-1 系统运行主界面

图4-2 创建二叉树界面

遍历二叉树

图4-3 二叉树递归遍历界面

4.2.详细代码分析

4.2.1主模块

本模块定义了系统运行主界面的相关内容和相关操作函数, 源代码如下: void main(){ BiTree T; T=NULL; int select;

//cout<<\"请按先序次序输入各结点的值, 以空格表示空树(输入时可连续输入):\"<cout<<\"\\n\\n请选择要执行的操作:\\n\"; cout<<\"1.创建二叉树\\n\";

cout<<\"2.二叉树的递归遍历算法（前、中、后）\\n\"; cout<<\"3.二叉树的层次遍历算法\\n\";

cout<<\"4.二叉树的非递归遍历算法（前、中、后）\\n\"; cout<<\"0.退出\\n\"; cin>>select; switch(select){ case 0:return; case 1:

遍历二叉树

cout<<\"请按先序次序输入各结点的值, 以空格表示空树(输入时可连续输入):\"<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(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 while }

4.2.2创建树模块

源代码如下:

void 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); } }

4.2.3遍历树模块

本模块包括了各种遍历二叉树的函数, 源代码如下:

void PreOrderTraverse(BiTree T) //二叉树的先序遍历(递归)成员函数声明 void InOrderTraverse(BiTree T) //二叉树的中序遍历(递归)成员函数声明 void PostOrderTraverse(BiTree T) //二叉树的后序遍历(递归)成员函数声明

void LevelOrderTraverse(BiTree T) // 二叉树的层序遍历(非递归)成员函数声明 void NRPreOrder(BiTree bt) // 二叉树的先序遍历(非递归)成员函数声明 void NRInOrder(BiTree bt) //二叉树的中序遍历(非递归)成员函数声明 void NRPostOrder(BiTree bt) //二叉树的后序遍历(非递归)成员函数声明

五、 调试分析

5.1.调试结果

5.1.1实验数据

A C B D E F

这棵树是随机画的, 由数据结构知识, 按照先序次序输入各个节点的值为: ABD###CEG###F#H##(此处#代表空格). 在程序中输入这些节点, 创建树, 如下图:

G H 遍历二叉树

5.1.2创建树界面

图5-1 创建树界面

5.1.3输出结果界面

输入2, 输出该二叉树递归遍历算法的遍历结果, 结果如下:

遍历二叉树

输入3, 输出该二叉树层序遍历算法的遍历结果, 结果如下:

输入4, 输出该二叉树非递归遍历算法的遍历结果, 结果如下:

六、总结

感谢老师的指导！同时感谢同学的帮助。

遍历二叉树

附录：程序代码

#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; } BTNode,* 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); } }

void PreOrderTraverse(BiTree T) //先序遍历 {

if(T) {

cout<data<<' ';

PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } }

void InOrderTraverse(BiTree T) //中序遍历 {

if(T) {

InOrderTraverse(T->lchild); cout<data<<' ';

遍历二叉树

InOrderTraverse(T->rchild); } }

void PostOrderTraverse(BiTree T) //后序遍历 {

if(T) {

PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<data<<' '; } }

void LevelOrderTraverse(BiTree T) //层序遍历 {

BiTree Q[MaxLength]; int front=0,rear=0; BiTree p;

if(T) //根结点入队 {

Q[rear]=T;

rear=(rear+1)%MaxLength; }

while(front!=rear) {

p=Q[front]; //队头元素出队 front=(front+1)%MaxLength; cout<data<<' ';

if(p->lchild) //左孩子不为空，入队 {

Q[rear]=p->lchild;

rear=(rear+1)%MaxLength; }

if(p->rchild) //右孩子不为空，入队 {

Q[rear]=p->rchild;

rear=(rear+1)%MaxLength; } } }

//非递归的先序遍历算法 void NRPreOrder(BiTree bt) {

BiTree stack[MaxLength],p; int top;

遍历二叉树

if (bt!=NULL) {

top=0; p=bt;

while(p!=NULL||top>0) {

while(p!=NULL) {

cout<data; stack[top]=p; top++;

p=p->lchild; }

if (top>0) {

top--;

p=stack[top]; p=p->rchild; } } } }

//非递归的中序遍历算法 void NRInOrder(BiTree bt) {

BiTree stack[MaxLength],p; int top;

if (bt!=NULL) {

top=0; p=bt;

while(p!=NULL||top>0) {

while(p!=NULL) {

stack[top]=p; top++;

p=p->lchild; }

if (top>0) {

top--;

p=stack[top]; cout<data; p=p->rchild;

遍历二叉树

} } } }

//非递归的后序遍历算法 typedef struct {

BiTree ptr; int tag; } stacknode;

void NRPostOrder(BiTree bt) {

stacknode s[MaxLength],x; BiTree p=bt; int top;

if(bt!=NULL) {

top=0; p=bt; do {

while (p!=NULL) //遍历左子树 {

s[top].ptr = p;

s[top].tag = 1; //标记为左子树 top++;

p=p->lchild; }

while (top>0 && s[top-1].tag==2) {

x = s[--top]; p = x.ptr;

cout<data; //tag为R，表示右子树访问完毕，故访问根结点 }

if (top>0) {

s[top-1].tag =2; //遍历右子树 p=s[top-1].ptr->rchild; } }

while (top>0); } }

遍历二叉树

int main() {

BiTree T; T=NULL; int select;

while(1) {

cout<<\"\\n\\n请选择要执行的操作:\\n\"; cout<<\"1.创建二叉树\\n\";

cout<<\"2.二叉树的递归遍历算法（前、中、后）\\n\"; cout<<\"3.二叉树的层次遍历算法\\n\";

cout<<\"4.二叉树的非递归遍历算法（前、中、后）\\n\"; cout<<\"0.退出\\n\"; cin>>select; switch(select) {

case 0:

return 0; case 1:

cout<<\"请按先序次序输入各结点的值，以空格表示空树(输入时可连续输入):\"<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(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\"; } } }