数据结构课程设计二叉树的遍历.docx
《数据结构课程设计二叉树的遍历.docx》由会员分享，可在线阅读，更多相关《数据结构课程设计二叉树的遍历.docx（17页珍藏版）》请在冰点文库上搜索。
数据结构课程设计二叉树的遍历
摘要之五兆芳芳创作
针对现实世界中许多关系庞杂的数据，如人类社会的家谱，各类社会组织机构,博弈交通等庞杂事物或进程以及客不雅世界中普遍存在的具有分支关系或条理特性的对象．如操纵系统的文件组成、人工智能和算法阐发的模型暗示以及数据库系统的信息组织形式等，用线性结构难以把其中的逻辑关系表达出来，必须借助于数和图这样的非线性结构，因此在以模拟客不雅世界问题，解决客不雅世界问题为主要任务的计较机领域中树型结构是信息的一种重要组织形式，树有着普遍应用.在树型结构的应用中又以二叉树最为经常使用.
二叉树是一种很是重要的非线性结构，所描述的数据有明显的条理关系，其中的每个元素只有一个前驱，二叉树是最为经常使用的数据结构，它的实际应用很是普遍，二叉树的遍历方法有三种，前序遍历，中序遍历，后序遍历，先序遍历的顺序为：
NLR先根结点，然后左子树，右子树；中序遍历顺序为；LNR先左子树，然后根结点，右子树；后序遍历顺序为：
LRN先左子树，然后右子树，根结点.由前序和中序遍历，有中序和后序遍历序列可以唯一确定一棵二叉树.对于给几个数据的排序或在已知的几个数据中进行查找，二叉树均能提供一种十分有效的办法，比方在查找问题上，任何借助于比较法查找长度为Ⅳ的一个序表的算法，都可以暗示成一株二叉树.反之，任何二叉树都对应一个查找有序表的有效办法按照树的数学理论，对于算法阐发的某些最有启发性的应用，是与给出用于计较各类类型中不合树的数目的公式有关的.
本文对二叉树以及二叉树的各类功效做介绍以及写出一些根本的程序，让我们对二叉树的理解有更好的效果.
关头词：
二叉树的遍历；左子树；右子树；递归
创建二叉树并遍历 根本要求：
该程序集成了如下功效：
（1）二叉树的成立
（2）递归和非递归先序，中序和后序遍历二叉树
（3）按条理遍历二叉树
（4）互换二叉树的左右子树
（5）输出叶子结点
（6）递归和非递归计较叶子结点的数目
分先序遍历，中序遍历和后序遍历三种情况考虑.
1.先序遍历，当二叉树非空时按以下顺序遍历，不然结束操纵：
1 拜访根结点；
2 按先序遍历法则遍历左子树；
3 按先序遍历法则遍历右子树；
2.中序遍历，当二叉树非空时按以下顺序遍历，不然结束操纵：
1 按中序遍历法则遍历左子树；
2 拜访根结点；
3 按中序遍历规3遍历右子树.
3.后序遍历，当二叉树非空时按以下顺序遍历，不然结束操纵：
1 按后序遍历法则遍历左子树；
2 按后序遍历法则遍历右子树；
3 拜访根结点.
对任意给定的二叉树（顶点数自定）成立它的二叉链表存贮结构，并利用栈的五种根本运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树的先序、中序、后序三种周游，输出三种周游的结果.
YES
YES
NO
NO
图1.1流程图
2.1数据结构设计：
1． 二叉树结点数据类型定义为：
template struct BiNode
{
BiNode*rchild,*lchild;//指向左孩子的指针
T data;//结点数据信息 };
2． 二叉树数据类型定义为：
template class BiTree {
template
friend ostream & operator <<（ostream &os ,BiTree &bt）; public:
BiTree（）;//无参机关函数
BiTree（int m）{};//有参空机关函数
BiTree（T ary[],int num,T none）;//有参机关函数
BiTree（）;//析构函数
void preorder（）;//递归前序遍历
void inorder（）;//递归中序遍历
void postorder（）;//递归后续遍历
void levelorder（）;//层序遍历
int count（）;//计较二叉树的结点数
void display（ostream &os）;//打印二叉树，有条理
void LevelNum（）;//计较每一层结点数
void PreOrder（）;//非递归前序遍历
void PostOrder（）;//非递归后序遍历
void creat（）;//创建二叉树
protected:
//以下函数供上面函数调用 //对应相同功效
Voidcreat（BiNode*&root）;//创建
void release（BiNode* &root）;//删除
BiNode * Build（T ary[],int num,T none,int idx）;//用数组创建二叉树
void PreOrder（BiNode* root）;//前序遍历
void PostOrder（BiNode* root）;//后续遍历
void LevelNum（BiNode* root）;//层序遍历
void preorder（BiNode* root）;//递归前序遍历
void inorder（BiNode* root）;//递归中序遍历
void postorder（BiNode* root）;//递归后续遍历
void levelorder（BiNode*root）;//层序遍历
int count（BiNode* root）;//计较结点数
void display（ostream& os,BiNode* root,int dep）;//打印
static bool leastCommanAncestor（BiNode *root, T va, T vb, BiNode
private:
BiNode *rootptr;
};
#include
usingnamespacestd;
//*************************************************************************************
//二叉树结点类的定义
template
structBTNode
{
Tdata;
BTNode*Lchild,*Rchild;
BTNode（TnodeValue=T（）,BTNode*leftNode=NULL,BTNode*rightNode=NULL）
:
data（nodeValue）,Lchild（leftNode）,Rchild（rightNode）{}//可选择参数的默认机关函数
};
//**************************************************************************************
//二叉树的成立
template
voidcreateBinTree（BTNode*&root）
{
BTNode*p=root;
BTNode*k;
TnodeValue;
cin>>nodeValue;
if（nodeValue==-1）
{
root=NULL;
}
else
{
root=newBTNode（）;
root->data=nodeValue;
createBinTree（root->Lchild）;
createBinTree（root->Rchild）;
}
}
//************************************************************************************
//二叉树的先序遍历
template
voidpreOrder（BTNode*&p）
{
if（p）
{
cout<data<<"";
preOrder（p->Lchild）;
preOrder（p->Rchild）;
}
}
//**************************************************************************************
//二叉树的中序遍历
template
voidinOrder（BTNode*&p）
{
if（p）
{
inOrder（p->Lchild）;
cout<data<<"";
inOrder（p->Rchild）;
}
}
//**************************************************************************************
//二叉树的后序遍历
template
voidlevelOrder（BTNode*&p）
{
if（p）
{
levelOrder（p->Lchild）;
levelOrder（p->Rchild）;
cout<data<<"";
}
}
//*************************************************************************************
//统计二叉树中结点的个数
template
intcountNode（BTNode*&p）
{
if（p==NULL）return0;
return1+countNode（p->Lchild）+countNode（p->Rchild）;
}
//***********************************************************************************
//求二叉树的深度
template
intdepth（BTNode*&p）
{
if（p==NULL）
return-1;
inth1=depth（p->Lchild）;
inth2=depth（p->Rchild）;
if（h1>h2）return（h1+1）;
returnh2+1;
}
//***********************************************************************************
//二叉树的消毁操纵
template
BTNode*destroy（BTNode*p）//消毁函数，用来消毁二叉树中的各个结点
{
if（p）
{
returndestroy（p->Lchild）;
returndestroy（p->Rchild）;
deletep;
}
}
//********************************************************************************
//主函数的设计
intmain（）
{
BTNode*rootNode=NULL;
intchoiced=0;
while（true）
{
system（"cls"）;
cout<<"\n\n\n---主界面---\n\n\n";
cout<<"1、创建二叉树2、先序遍历二叉树\n";
cout<<"3、中序遍历二叉树4、后序遍历二叉树\n";
cout<<"5、统计结点总数6、查抄树深度\n";
cout<<"7、消毁二叉树0、退出\n\n";
cout<<"请选择操纵：
";
cin>>choiced;
if（choiced==0）
return0;
elseif（choiced==1）
{
system（"cls"）;
cout<<"请输入每个结点，回车确认，并以-1结束：
\n";
createBinTree（rootNode）;
}
elseif（choiced==2）
{
system（"cls"）;
cout<<"先序遍历二叉树结果：
\n";
preOrder（rootNode）;
cout<system（"pause"）;
}
elseif（choiced==3）
{
system（"cls"）;
cout<<"中序遍历二叉树结果：
\n";
inOrder（rootNode）;
cout<system（"pause"）;
}
elseif（choiced==4）
{
system（"cls"）;
cout<<"后序遍历二叉树结果：
\n";
levelOrder（rootNode）;
cout<system（"pause"）;
}
elseif（choiced==5）
{
system（"cls"）;
intcount=countNode（rootNode）;
cout<<"二叉树中结点总数为"<system（"pause"）;
}
elseif（choiced==6）
{
system（"cls"）;
intdep=depth（rootNode）;
cout<<"此二叉树的深度为"<system（"pause"）;
}
elseif（choiced==7）
{
system（"cls"）;
cout<<"二叉树已被消毁！
\n";
destroy（rootNode）;
cout<system（"pause"）;
}
else
{
system（"cls"）;
cout<<"\n\n\n\n\n\t错误选择！
\n";
}
}
}
创建二叉树：
依次输入二叉树前序遍历序列，构建相应的二叉树.
二叉树遍历：
递归算法、非递归算法测试，调用相应函数进行测试，结果正确. 求二叉树深度和结点数：
创建一个二叉树，调用相关函数，测试结果正确. 计较每层结点数：
调用levelNum（）函数，测试结果正确.
调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时，容易进入死循环，经过查找资料、分步伐试最终找到循环结束条件，顺利解决各个难题.
（1）初始界面:
主界面所包含的内容
（2）运行结果：
进行操纵1，输入每个结点，显示结果如下
进行操纵2，执行结果如下：
进行操纵3，执行结果如下：
进行操纵4，执行结果如下：
图4.5二叉树后序遍历:
进行操纵5，执行结果如下：
进行操纵6，执行结果如下：
总结
要能很好的掌握编程,仅仅通过几个复杂的程序的编写时无法达成的,更需要大量堆集和深入才可能通过本次课程设计.有关一个课题的所有知识不但仅是在课本上，多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能力.本次课程设计还让我认识到自己的缺点.本次选的课题是二叉树的遍历，因为本学期所学的就是二叉树等数据结构，所以认为比较适合.刚开始认为会很复杂，但到后来就出现一些难以解决的问题，就像老师请教，并查阅相关资料.经过慢慢的调试，最终测试成功.
这次课程设计让我所学到的数据结构知识阐扬的淋漓尽致，并且还拓展了我的知识面，使我加倍熟练的掌握各类办法.
总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据结构加倍了解.
参考文献
[1]严蔚敏吴伟民《数据结构（C语言版）》清华大学出版社，2009年9月
[2]谭浩强《C程序设计（第三版）》清华大学出版社2009年1月
升级会员 