数据结构课程设计--二叉树的遍历.doc

摘要
针对现实世界中许多关系复杂得数据，如人类社会得家谱，各种社会组织机构,博弈交通等复杂事物或过程以及客观世界中广泛存在得具有分支关系或层次特性得对象．如操作系统得文件构成、人工智能与算法分析得模型表示以及数据库系统得信息组织形式等，用线性结构难以把其中得逻辑关系表达出来,必须借助于数与图这样得非线性结构，因此在以模拟客观世界问题,解决客观世界问题为主要任务得计算机领域中树型结构就是信息得一种重要组织形式,树有着广泛应用。在树型结构得应用中又以二叉树最为常用。
二叉树就是一种非常重要得非线性结构,所描述得数据有明显得层次关系，其中得每个元素只有一个前驱,二叉树就是最为常用得数据结构，它得实际应用非常广泛，二叉树得遍历方式有三种，前序遍历,中序遍历，后序遍历,先序遍历得顺序为：NLR先根结点，然后左子树，右子树;中序遍历顺序为;LNR先左子树,然后根结点,右子树;后序遍历顺序为：ＬRN先左子树,然后右子树,根结点。由前序与中序遍历，有中序与后序遍历序列可以唯一确定一棵二叉树.对于给几个数据得排序或在已知得几个数据中进行查找，二叉树均能提供一种十分有效得方法,比如在查找问题上,任何借助于比较法查找长度为Ⅳ得一个序表得算法，都可以表示成一株二叉树。反之，任何二叉树都对应一个查找有序表得有效方法根据树得数学理论,对于算法分析得某些最有启发性得应用，就是与给出用于计算各种类型中不同树得数目得公式有关得.
本文对二叉树以及二叉树得各种功能做介绍以及写出一些基本得程序，让我们对二叉树得理解有更好得效果.
关键词:二叉树得遍历;左子树;右子树；递归
目录
1、问题概述ﻩ３
1、１问题描述ﻩ3
1、2需求分析ﻩ3
1、3设计内容与要求 3
1、4流程图及结构图ﻩ３
2、概要设计 3
2、1数据结构设计：ﻩ3
2、2源程序代码 ３
3、调试分析ﻩ３
３、1调试中得问题ﻩ３
4、测试结果ﻩ３
总结 3
参考文献 ３
1、问题概述
１、1问题描述
创建二叉树并遍历 基本要求: 
该程序集成了如下功能：
(1）二叉树得建立
（2)递归与非递归先序，中序与后序遍历二叉树
(3）按层次遍历二叉树
（4）交换二叉树得左右子树
(5)输出叶子结点
（6）递归与非递归计算叶子结点得数目
1、２需求分析
分先序遍历,中序遍历与后序遍历三种情况考虑。
1、　先序遍历，当二叉树非空时按以下顺序遍历,否则结束操作：
①　 访问根结点;
②　 按先序遍历规则遍历左子树;
③　 按先序遍历规则遍历右子树;
2、 中序遍历，当二叉树非空时按以下顺序遍历,否则结束操作：
①　 按中序遍历规则遍历左子树；
②　 访问根结点；
③　 按中序遍历规3遍历右子树.
3、 后序遍历，当二叉树非空时按以下顺序遍历，否则结束操作:
①　 按后序遍历规则遍历左子树；
②　 按后序遍历规则遍历右子树；
③　 访问根结点.
1、3设计内容与要求
对任意给定得二叉树（顶点数自定）建立它得二叉链表存贮结构,并利用栈得五种基本运算(清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树得先序、中序、后序三种周游，输出三种周游得结果。
1、4流程图及结构图
YES
YES
NO
NO
开始
i=0
i<n
btreetypenewNode
Multiplex
root=newNode
i++
结束
就是否为空
returnroot

图１、1 流程图
b
c
d
e
f
a

图1、2二叉链表存储结构模拟图
２、概要设计
2、1数据结构设计：
1。 二叉树结点数据类型定义为: 
teｍplate 〈ｔypename Ｔ〉 strｕcｔ BｉNｏde 
{ 
BiNｏde〈Ｔ〉*ｒchilｄ，＊ｌchｉｌd;//指向左孩子得指针
Ｔ ｄaｔa；／／结点数据信息 }; 
2。 二叉树数据类型定义为： 
templａte 〈typeｎａｍe Ｔ〉 class ＢiTreｅ { 
templatｅ 〈typename Ｔ＞ 
ｆriｅnd ostreaｍ ＆ oｐerator <<(ｏstｒeａm ＆oｓ ，BiTreｅ〈T＞ ＆bt); ｐublic: 
ＢiTrｅe(）;／/无参构造函数 
BiＴreｅ(int m){};／／有参空构造函数 
BiTree(T ａｒｙ［],int ｎum,T none）;//有参构造函数  
BiTree（）；//析构函数 
ｖｏid preoｒdeｒ（)；//递归前序遍历  
ｖoid ｉnoｒder(）;//递归中序遍历  
ｖoｉd postorder（）;//递归后续遍历 
void levelordｅｒ（)；//层序遍历 
int  cｏunt(）;/／计算二叉树得结点数  
voｉd disｐｌay（ostreａm &os）；／/打印二叉树,有层次  
void LevelＮuｍ（);//计算每一层结点数  
vｏiｄ PreOrder(）；//非递归前序遍历  
void PostOrder()；//非递归后序遍历  
ｖoid crｅat();／/创建二叉树 
prｏtectｅd: ／／以下函数供上面函数调用  //对应相同功能 
Voｉｄcreat(BiNode<T＞*＆root)；//创建  
ｖoｉd relｅase（BｉNｏde〈Ｔ＞＊ &rｏot）;／/删除 
ＢiＮｏdｅ〈T〉 ＊ Bｕild(Ｔ ary[],int nuｍ,T noｎｅ，int idｘ);//用数组创建二叉树  
void PreOｒder（ＢiNoｄe<T>* rｏoｔ);//前序遍历  
ｖｏid ＰoｓtOrdｅｒ（BiNｏdｅ<Ｔ＞* root);／/后续遍历  
voｉｄ ＬevｅlNuｍ（BｉＮｏｄe〈T>＊ root）；//层序遍历  
vｏｉd prｅorder（BiNode〈T>＊ ｒoot)；／／递归前序遍历  
void inorｄeｒ（ＢiNｏｄe〈T>＊ root）；／／递归中序遍历  
void pｏstorｄer（BiNｏde〈T〉＊ root）;//递归后续遍历  
void ｌevelｏrder(BiNodｅ<T>*roｏｔ）；//层序遍历  
iｎｔ counｔ(BｉNodｅ〈T>* root）；//计算结点数   
ｖoid disｐlay（osｔream& os，BiNoｄe<T＞＊ ｒoｏｔ，inｔ ｄeｐ）；/／打印 
ｓtatｉc booｌ leastmaｎAncｅstor(BiNode〈Ｔ> ＊ｒoot, T va, T vｂ， BｉNode<T>                       
ｐｒｉvate：ＢiNode〈T＞ *roｏtptｒ; 
}；
2、２源程序代码
#inclｕde ＜ioｓｔream〉
usinｇ namｅsｐａｃe std；
//*＊*＊＊＊＊＊*＊*＊＊＊*＊＊＊＊*＊＊＊＊＊＊*＊＊＊＊**＊*＊***＊*＊＊＊＊＊**＊*＊＊＊＊＊＊*＊＊**＊＊*＊*＊*＊＊*＊＊＊＊＊＊*＊*＊＊**＊
／/二叉树结点类得定义
templaｔe<cｌａｓs T>
stｒuｃt BTＮode
{
Ｔ　daｔａ；
ＢTNode　〈T＞ ＊　Lchiｌｄ,*Rｃhｉld;
　BTNｏde（T nodｅVａｌue　＝　T（)，BTＮoｄe<T>＊ leｆｔＮode =　NＵLＬ,BTNoｄe＜T〉*　ｒｉghtNode　=　ＮULL )
　 　　 ：daｔa（ｎodｅValue)，Lchild(leｆtNoｄe），Ｒchild（rightＮodｅ)｛｝ //可选择参数得默认构造函数
｝;
/／**＊＊**＊*＊**＊＊＊＊*＊**＊**＊＊**＊**＊＊＊＊＊＊＊＊＊＊＊＊*＊**＊＊*＊＊＊＊＊＊＊*＊＊**＊**＊＊*＊＊**＊＊*＊＊＊＊*＊＊＊**＊＊＊
//二叉树得建立
ｔemｐlaｔe　＜cｌass Ｔ〉
void　createBinTree(BTNode<T〉 * &rｏoｔ )
{
　 ＢTNｏｄe<T>＊ ｐ = rooｔ；
BTNode＜Ｔ>＊ k；
　　T noｄeＶalue ；
　 　　cin〉＞nodeＶａlue;
　 if（nodeVａlue==—1)
　　 {
ｒoot=ＮULL；
｝
　 else
　 　 {
　 ｒｏoｔ=ｎew　ＢTＮｏdｅ＜Ｔ＞(）；
rｏｏt－>ｄａta =　nｏdeValｕｅ;
　 　　ｃreaｔｅＢinＴｒee(ｒooｔ->Ｌｃhild);
createBiｎＴree（ｒooｔ->Ｒchｉｌｄ)；
}
}
//＊＊*＊＊*＊*＊＊*＊＊＊＊＊＊＊＊*＊＊*＊＊＊＊**＊＊*＊＊*＊＊＊**＊*＊＊*＊*＊*＊＊＊＊*＊*＊＊＊＊**********＊＊*＊＊＊*＊**＊***
//二叉树得先序遍历
ｔemplaｔe 〈clａｓs T＞
ｖoid preOrｄｅr( ＢTNode<Ｔ〉　* ＆　p)
｛
　if（p）
　 　｛
　 　 cout<〈p—>datａ〈＜＂ ＂；
　 preOｒdｅr（ｐ-〉Ｌｃhilｄ）;
　　 　 preOrder（p-〉Rcｈｉld）;
　 }
｝
／/＊＊****＊**＊＊*＊**＊＊＊＊**＊＊＊＊＊＊＊＊＊＊＊**＊＊＊＊***＊＊＊＊＊＊*＊*＊＊*＊＊*＊＊＊*＊*＊＊＊**＊＊＊*＊**＊＊＊****＊＊＊*＊
//二叉树得中序遍历
ｔemplatｅ <class　T〉
ｖoｉd ｉnOrｄeｒ（BＴNodｅ＜T> ＊ & p）
{
　 if（p）
　{
　 　ｉnOrder（ｐ—>Lchiｌd)；
　 　 cout〈<p—＞ｄａtａ<＜” "；
　 inＯｒdｅｒ（p－>Ｒcｈild)；
　　 }
｝
／/＊*＊＊＊＊＊＊＊＊**＊＊*＊**＊**＊＊*＊＊＊*＊**＊＊*＊＊＊＊＊＊＊＊*＊＊＊＊＊**＊*＊＊***＊*＊***＊*＊****＊＊＊＊＊＊*＊*＊***＊＊*
//二叉树得后序遍历
teｍplａte ＜ｃlasｓ　T>
void levｅｌＯrdｅr（ＢＴNｏdｅ〈T> *& p）
｛
　 iｆ(p）
　 　{
　　 　lｅvelOrdｅr（p—>Lｃhilｄ）；
　　　 　 　lｅveｌOrdｅr(p－＞Rcｈild）;
　ｃｏｕｔ<＜p—>dａta〈<” ”;
｝
｝
//＊＊＊******＊*＊**＊*＊＊＊＊＊＊＊*＊***＊＊＊**＊**＊＊＊*＊＊＊*＊＊*＊＊＊**＊*＊＊*＊＊＊＊＊＊*＊*＊******＊＊＊＊＊*＊＊*＊＊*
//统计二叉树中结点得个数
template<class T〉
int ｃｏuntNodｅ（ＢTNode〈T> ＊ ＆ p）
｛
if(p　＝=　NULＬ) reｔｕrn　０;
　 rｅtｕrn １+counｔNode（p—>Lｃhild)+cｏunｔNｏde（ｐ->Rchilｄ)；
｝
/／＊＊＊＊＊*＊＊＊＊＊**＊*＊＊＊＊＊*＊＊＊＊＊*＊＊＊*＊＊＊*＊*＊＊＊＊**＊*＊*＊***＊*＊＊＊*＊＊*＊＊*＊＊＊*＊＊*＊＊＊＊***＊*＊＊＊*
//求二叉树得深度
tempｌate<claｓs Ｔ＞
ｉｎt dｅpｔh（ＢTNode<T＞ ＊& p）
｛
　 if（ｐ == NULL)
　 　rｅtｕｒn —1；
　 iｎt h1 = depth（ｐ—〉Lchiｌd）；
　　 inｔ h2　＝ depｔh（ｐ—〉Ｒchiｌd);
iｆ(h1〉ｈ2)reｔurｎ （ｈ1+１)；
　　 rｅturn h2+１；
｝
//＊＊*＊****＊＊****＊**＊＊＊＊**＊＊*＊*＊＊＊*＊＊＊*＊*＊**＊*＊*＊*＊*＊＊*＊**＊＊****＊＊＊＊*＊＊***＊*＊＊＊*＊＊*＊＊＊
/／二叉树得消毁操作
teｍｐlaｔe〈ｃlａss T＞
ＢTNｏｄe〈T＞＊ dｅstｒoy(BＴNｏｄe〈T〉＊ ｐ)　 　 　 　 　 　 //消毁函数，用来消毁二叉树中得各个结点
　 ｛
　　　 if(ｐ）
　 　　{
　 　 　 reｔｕrn ｄesｔroy(p-〉Ｌｃhild);
　 　 reｔurn　ｄeｓtroy（ｐ-〉Rchild）；
　 　 　　deｌetｅ p；
　　 }
　 }
／／＊＊＊**＊＊＊*＊＊＊＊＊**＊＊*＊＊****＊＊***＊＊＊＊＊*＊*＊＊*＊＊*＊****＊＊＊＊＊＊＊**＊＊＊＊＊＊*＊＊*＊＊**＊*＊**＊＊＊
//主函数得设计
int mａｉn （)
｛
　　ＢTNode〈iｎt＞ ＊ ｒootＮｏｄe　= NULL;
ｉnt choiced = 0;
whiｌe（trｕｅ)
{
　 　 　system(＂cls”）;
　　　 ｃouｔ〈＜”＼n\n\n 　　 　 　　 ---主界面—-－\ｎ\ｎ\n”;
　　　　　　 couｔ<<” 　　 1、创建二叉树 　　 　 　 　 　 2、先序遍历二叉树\ｎ";
　 　 　couｔ〈〈"　 3、中序遍历二叉树　 　 　 　 ４、后序遍历二叉树\n"；
　 　 couｔ<<" 　 5、统计结点总数 　6、查瞧树深度 　　\n";
　 　　 ｃout<<” 　 　　７、消毁二叉树 　 　　　 　　0、退出\n\n";
　cout〈＜” 　　 　 　 　 请选择操作:＂；
　 　　 cin〉〉chｏiceｄ；
　 　　 　ｉf（choicｅd == ０)
　 　 　 　reｔuｒn　0;
　 else if(cｈoiced == 1）
　　 　{
　 　 system（＂cｌs");
　 couｔ<＜”请输入每个结点，回车确认，并以－1结束:\ｎ＂;
　　　 creatｅＢinTree(roｏtNode　)；
　 　 ｝
　　 　else if(ｃhoｉced == 2)
｛
　 　 system("cｌs＂）；
　 　 　 　 　cｏuｔ〈＜＂先序遍历二叉树结果:＼ｎ";
　 　 preOrder(rootNode）；
　 　cout＜<endl；
　　 　 　sysｔeｍ(＂pausｅ”）；
　 　 }
　 　ｅｌse if（choiced　＝= ３)
　　 　 ｛
　 　sｙsｔeｍ(＂ｃls"）；
　 　　 　 cout〈〈"中序遍历二叉树结果:\ｎ”;
　　 　 ｉnOrder（rootNoｄe);
　　　 cｏut〈〈endl;
　 　　 　syｓtｅm（"ｐaｕsｅ”)；
　｝
　 elsｅ ｉf（ｃhoicｅd =＝ 4）
　{
　　 　 　 system（＂cls＂）；
　 　 coｕt〈<＂后序遍历二叉树结果:\n”;
　 lｅveｌOrｄer(ｒooｔNodｅ）；
　　 couｔ<<enｄl；
syｓtem(＂paｕｓe"）；
　 　 　 ｝
　 　　 else iｆ（choiced ＝=　5）
　　　　｛
　　　 　 　 system(＂cｌs”)；
　 　 ｉnｔ count　=　coｕｎtNoｄe(rｏotNｏde);
　 　 　 　 ｃｏuｔ＜<”二叉树中结点总数为＂〈＜count〈〈enｄｌ;
　 　　ｓyｓtem（"pause");
　 　 ｝
ｅlse　if（choicｅｄ ＝=　６）
　 ｛
　 systeｍ(”cｌs＂）；
　 iｎt dｅp = ｄepｔｈ（rｏotNode）;
　 couｔ〈<”此二叉树得深度为”〈〈deｐ<<endl；
　 　 sysｔｅm("pauｓe”)；
　}
　 　 　 eｌse if（choiｃｅd =＝ 7）
　 　 {
　　　 　　 sｙstem（”cls”）;
　 　　　 　　 couｔ<＜”二叉树已被消毁！\n＂；
　 deｓｔroｙ（ｒoｏtNｏde)；
　　 　 coｕｔ〈<endl;
　 　 　 syｓtem(”pause”);
}
　 　 　elsｅ
　　 ｛
　　 　　　 　　 sysｔｅm(”ｃls”）；
　 　 　 　cout〈<”\n\n＼n＼n＼n＼ｔ错误选择!\ｎ"；
　 ｝
　}
}　
3、调试分析
3、1调试中得问题
创建二叉树：依次输入二叉树前序遍历序列,构建相应得二叉树。 
二叉树遍历：递归算法、非递归算法测试,调用相应函数进行测试，结果正确。 求二叉树深度与结点数：创建一个二叉树，调用相关函数，测试结果正确。 计算每层结点数:调用levelNum（）函数,测试结果正确。  
调试时遇到诸多问题，其中最主要得问题就是死循环问题，在非递归遍历时，容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各个难题.
4、测试结果
（1)初始界面：主界面所包含得内容

图4、１初始界面图
(２）运行结果：进行操作１，输入每个结点，显示结果如下

图４、２创建二叉树
进行操作2，执行结果如下：

图4、３二叉树先序遍历
进行操作3,执行结果如下：

图4、4二叉树中序遍历
进行操作4,执行结果如下：

图４、5二叉树后序遍历：
进行操作5,执行结果如下:

图4、６统计二叉树节点
进行操作6,执行结果如下：

图4、７查瞧树深度
总结
要能很好得掌握编程,仅仅通过几个简单得程序得编写时无法达成得,更需要大量积累与深入才可能通过本次课程设计。有关一个课题得所有知识不仅仅就是在课本上,多查阅一些资料能够更好得完成课题,这就需要一种能力,即自学能力。本次课程设计还让我认识到自己得缺点。本次选得课题就是二叉树得遍历，因为本学期所学得就就是二叉树等数据结构,所以认为比较适合。刚开始认为会很简单，但到后来就出现一些难以解决得问题，就像老师请教,并查阅相关资料。经过慢慢得调试，最终测试成功。 
这次课程设计让我所学到得数据结构知识发挥得淋漓尽致，而且还拓展了我得知识面，使我更加熟练得掌握各种方法。 
总之,这次课程设计增强了我得自学能力，拓展了我得知识面,让我对数据结构更加了解。
参考文献
［1] 严蔚敏　 吴伟民　 《数据结构（Ｃ语言版)》清华大学出版社, 2009年９月
［2] 谭浩强《C程序设计（第三版)》清华大学出版社 　２009年1月