数据结构课程设计报告_遍历二叉树

数据结构课程设计报告_遍历⼆叉树

XXXX⼤学

《数据结构》课程设计

报告

课题名称: 遍历⼆叉树

系（院）:

专业:

班级:

组员姓名:

学号:

指导教师:

开课时间: 学年学期

摘要

树结构在客观世界中⼴泛存在, 如⼈类社会的族谱和各种社会组织机构都可⽤树形象表⽰. 树在计算机领域中也得到⼴泛应⽤,如在编译源程序时, 可⽤树表⽰源程序的语法结构. ⼜如在数据库系统中, 树型结构也是信息的重要组织形式之⼀. ⼀切具有层次关系的问题都可⽤树来描述.

针对这样的问题, 我选择了⼆叉树的遍历作为我的课程设计主题, 编写程序, 实现对⼆叉树的遍历. 在本次课程设计中, ⼆叉树的建⽴使⽤了递归算法；在前序、中序和后续遍历的算法中则同时使⽤了递归与⾮递归的算法, 即在这些遍历算法的实现中使⽤了栈结构与队列结构, 提供了6种不同的遍历⽅式, 供使⽤者选择. 同时, 该程序具有输出层序遍历的功能, 层序遍历模块使⽤了⾮递归算法. 该程序基本实现了对⼆叉树的遍历, 对于递归与⾮递归算法, 我们应从实际应⽤中体验这些算法的优越性.

关键词: 层次关系, ⼆叉树建⽴, 递归与⾮递归, 遍历, 栈, 队列

⽬录

⼀、问题描述 (1)

⼆、需求分析 (1)2.1主功能模块 (1)

2.2创建树模块 (1)

2.3遍历树模块 (1)

三、概要设计 (2)3.1主界⾯设计思想流程图 (2)

3.2. 创建⼆叉树 (2)

3.2.1⼆叉树创建的思想 (2)

3.2.2⼆叉树创建的算法流程图 (2)

3.3.先序递归遍历 (3)

3.3.1先序递归遍历思想 (3)

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

3.4.中序递归遍历 (3)

3.4.1中序递归遍历思想 (3)3.4.2中序递归遍历的算法流程图 (4)

3.5.后序递归遍历 (4)

3.5.1后序递归遍历思想 (4)

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

3.6.先序⾮递归遍历 (5)

3.6.1先序⾮递归遍历思想 (5)

3.6.2先序⾮递归遍历的算法流程图 (6)

3.7.中序⾮递归遍历 (6)

3.7.1中序⾮递归遍历思想 (6)

3.7.2中序⾮递归遍历的算法流程图 (7)

3.8.后序⾮递归遍历 (7)

3.8.1后序⾮递归遍历思想 (7)

3.8.2后序⾮递归遍历的算法流程图 (8)

3.9.层序⾮递归遍历 (8)

3.9.1层序⾮递归遍历思想 (8)

3.9.2层序⾮递归遍历的算法流程图 (9)

四、详细设计 (10)4.1界⾯设计 (10)

4.2.详细代码分析 (11)

4.2.1主模块 (11)

4.2.2创建树模块 (12)

4.2.3遍历树模块 (13)

五、调试分析 (13)5.1.调试结果 (13)

5.1.1实验数据 (13)

5.1.2创建树界⾯ (14)

5.1.3输出结果界⾯ (14)

5.2.算法分析 (16)

5.2.1时间复杂度 (16)

5.2.2空间复杂度 (16)

5.3.程序的不⾜ (16)

5.3.1程序不⾜之处 (16)

六、⼼得体会 (17)

七、参考⽂献 (17)

⼀、问题描述建⽴⼆叉树, 层序、先序、中序、后序遍历.(⽤递归或⾮递归的⽅法都可以)

要求能够输⼊树的各个结点, 并能够输出⽤不同⽅法遍历的遍历序列；分别建⽴⼆叉树存储结构的的输⼊函数、输出层序遍历序列的函数、输出先序遍历序列的函数、输出中序遍历序列的函数、输出后序遍历序列的函数.

⼆、需求分析

在现实世界层次化的数据模型中, 数据与数据之间的关系纷繁复杂. 其中很多关系⽆法使⽤简单的线性结构表⽰清楚, ⽐如祖先与后代的关系、整体与部分的关系等. 于是⼈们借鉴⾃然界中树的形象创造了⼀种强⼤的⾮线性结构——树. 树形结构的具体形式有很多种, 其中最常⽤的就是⼆叉树. ⽽⼆叉树的多层次遍历遍历则是⼆叉树的重要内容.

本程序⽤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先序递归遍历的算法流程图

3.4.中序递归遍历

3.4.1中序递归遍历思想

若⼆叉树为空, 则空操作；否则(1)中序遍历左⼦树；

(2)访问根结点；

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

void InOrderTraverse(BiTree T)

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

3.5.后序递归遍历

3.5.1后序递归遍历思想

若⼆叉树为空, 则空操作；否则(1)后序遍历左⼦树；

(2)后序遍历右⼦树；

(3)访问根结点. 相关函数如下:void PostOrderTraverse(BiTree T)3.6.先序⾮递归遍历

3.6.1先序⾮递归遍历思想

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

(2)指针指向p的左孩⼦结点；

(3)从栈中弹出栈顶元素；

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

3.7.中序⾮递归遍历

3.7.1中序⾮递归遍历思想

(1)指针指向p的左孩⼦结点；

(2)从栈中弹出栈顶元素；

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

(4)指针指向p的右孩⼦结点. 相关函数如下:

void NRInOrder(BiTree bt)

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

3.8.后序⾮递归遍历

3.8.1后序⾮递归遍历思想

若⼆叉树为空, 则空操作；否则引⼊栈和标记模拟递归⼯作栈, 初始时栈为空. 相关函

数如下: void NRPostOrder(BiTree bt);3.8.2后序⾮递归遍历的算法流程图

3.9.层序⾮递归遍历

3.9.1层序⾮递归遍历思想

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

(2)若该元素所指结点的左右孩⼦结点⾮空, 则该元素所指结点的左孩⼦指针和右孩⼦指针顺序⼊队. 相关函数如下:

void LevelOrderTraverse(BiTree T)

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

四、详细设计4.1界⾯设计图4-1 系统运⾏主界⾯

图4-2 创建⼆叉树界⾯

图4-3 ⼆叉树递归遍历界⾯4.2.详细代码分析

4.2.1主模块

本模块定义了系统运⾏主界⾯的相关内容和相关操作函数, 源代码如下:void main(){

BiTree T;

T=NULL;

int select;//cout<<"请按先序次序输⼊各结点的值, 以空格表⽰空树(输⼊时可连续输⼊):"<

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;

case 1:

cout<<"请按先序次序输⼊各结点的值, 以空格表⽰空树(输⼊时可连续输⼊):"<

CreateBiTree(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(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) //⼆叉树的后序遍历(⾮递归)成员函数声明

五、调试分析