数据结构优秀课程设计二叉树的遍历.docx

摘要
针对现实世界中很多关系复杂数据，如人类社会家谱，多种社会组织机构,博弈交通等复杂事物或过程和客观世界中广泛存在含有分支关系或层次特征对象．如操作系统文件组成、人工智能和算法分析模型表示和数据库系统信息组织形式等，用线性结构难以把其中逻辑关系表示出来，必需借助于数和图这么非线性结构，所以在以模拟客观世界问题，处理客观世界问题为关键任务计算机领域中树型结构是信息一个关键组织形式，树有着广泛应用。在树型结构应用中又以二叉树最为常见。
二叉树是一个很关键非线性结构，所描述数据有显著层次关系，其中每个元素只有一个前驱，二叉树是最为常见数据结构，它实际应用很广泛，二叉树遍历方法有三种，前序遍历，中序遍历，后序遍历，先序遍历次序为：NLR先根结点，然后左子树，右子树；中序遍历次序为；LNR先左子树，然后根结点，右子树；后序遍历次序为：LRN先左子树，然后右子树，根结点。由前序和中序遍历，有中序和后序遍历序列能够唯一确定一棵二叉树。对于给多个数据排序或在已知多个数据中进行查找，二叉树均能提供一个十分有效方法，比如在查找问题上，任何借助于比较法查找长度为Ⅳ一个序表算法，全部能够表示成一株二叉树。反之，任何二叉树全部对应一个查找有序表有效方法依据树数学理论，对于算法分析一些最有启发性应用，是和给出用于计算多种类型中不一样树数目标公式相关。
本文对二叉树和二叉树多种功效做介绍和写出部分基础程序，让我们对二叉树了解有愈加好效果。

关键词：二叉树遍历；左子树；右子树；递归

目录
1.问题概述 3
1.1问题描述 3
1.2需求分析 3
1.3设计内容和要求 3
1.4步骤图及结构图 3
2.概要设计 3
2.1数据结构设计： 3
2.2源程序代码 3
3.调试分析 3
3.1调试中问题 3
4.测试结果 3
总结 3
参考文件 3

1.问题概述
1.1问题描述
创建二叉树并遍历 基础要求： 
该程序集成了以下功效：
（1）二叉树建立
（2）递归和非递归先序，中序和后序遍历二叉树
（3）按层次遍历二叉树
（4）交换二叉树左右子树
（5）输出叶子结点
（6）递归和非递归计算叶子结点数目
1.2需求分析
分先序遍历，中序遍历和后序遍历三种情况考虑。
1. 先序遍历，当二叉树非空时按以下次序遍历，不然结束操作：
①　 访问根结点；
②　 按先序遍历规则遍历左子树；
③　 按先序遍历规则遍历右子树；
2. 中序遍历，当二叉树非空时按以下次序遍历，不然结束操作：
①　 按中序遍历规则遍历左子树；
②　 访问根结点；
③　 按中序遍历规3遍历右子树。
3. 后序遍历，当二叉树非空时按以下次序遍历，不然结束操作：
①　 按后序遍历规则遍历左子树；
②　 按后序遍历规则遍历右子树；
③　 访问根结点。

1.3设计内容和要求
对任意给定二叉树（顶点数自定）建立它二叉链表存贮结构，并利用栈五种基础运算（清空堆栈、压栈、弹出、取栈顶元素、判栈空）实现二叉树先序、中序、后序三种周游，输出三种周游结果。

1.4步骤图及结构图

YES
YES
NO
NO
开始
i=0
i<n
btreetypenewNode
Multiplex
root=newNode
i++
结束
是否为空
returnroot

图1.1 步骤图
b
c
d
e
f
a

图1.2二叉链表存放结构模拟图

2.概要设计
2.1数据结构设计：
1． 二叉树结点数据类型定义为： 
template <typename T> struct BiNode 
{ 
BiNode<T>*rchild,*lchild;//指向左孩子指针
T data;//结点数据信息 }; 
2． 二叉树数据类型定义为： 
template <typename T> class BiTree { 
template <typename T> 
friend ostream & operator <<(ostream &os ,BiTree<T> &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<T>*&root);//创建  
void release(BiNode<T>* &root);//删除 
BiNode<T> * Build(T ary[],int num,T none,int idx);//用数组创建二叉树  
void PreOrder(BiNode<T>* root);//前序遍历  
void PostOrder(BiNode<T>* root);//后续遍历  
void LevelNum(BiNode<T>* root);//层序遍历  
void preorder(BiNode<T>* root);//递归前序遍历  
void inorder(BiNode<T>* root);//递归中序遍历  
void postorder(BiNode<T>* root);//递归后续遍历  
void levelorder(BiNode<T>*root);//层序遍历  
int count(BiNode<T>* root);//计算结点数   
void display(ostream& os,BiNode<T>* root,int dep);//打印 
static bool leastCommanAncestor(BiNode<T> *root, T va, T vb, BiNode<T>                       
private:BiNode<T> *rootptr; 
};

2.2源程序代码
#include <iostream>
using namespace std;
//*************************************************************************************
//二叉树结点类定义
template<class T>
struct BTNode
{
T data;
BTNode <T> * Lchild,*Rchild;
BTNode(T nodeValue = T(),BTNode<T>* leftNode = NULL,BTNode<T>* rightNode = NULL )
:data(nodeValue),Lchild(leftNode),Rchild(rightNode){} //可选择参数默认结构函数
};
//**************************************************************************************
//二叉树建立
template <class T>
void createBinTree(BTNode<T> * &root )
{
BTNode<T>* p = root;
BTNode<T>* k;
T nodeValue ;
cin>>nodeValue;
if(nodeValue==-1)
{
root=NULL;
}
else
{
root=new BTNode<T>();
root->data = nodeValue;
createBinTree(root->Lchild);
createBinTree(root->Rchild);
}
}
//************************************************************************************
//二叉树先序遍历
template <class T>
void preOrder( BTNode<T> * & p)
{
if(p)
{
cout<<p->data<<" ";
preOrder(p->Lchild);
preOrder(p->Rchild);
}
}
//**************************************************************************************
//二叉树中序遍历
template <class T>
void inOrder(BTNode<T> * & p)
{

if(p)
{
inOrder(p->Lchild);
cout<<p->data<<" ";
inOrder(p->Rchild);
}
}
//**************************************************************************************
//二叉树后序遍历
template <class T>
void levelOrder(BTNode<T> *& p)
{
if(p)
{
levelOrder(p->Lchild);
levelOrder(p->Rchild);
cout<<p->data<<" ";
}
}
//*************************************************************************************
//统计二叉树中结点个数
template<class T>
int countNode(BTNode<T> * & p)
{
if(p == NULL) return 0;
return 1+countNode(p->Lchild)+countNode(p->Rchild);
}
//***********************************************************************************
//求二叉树深度
template<class T>
int depth(BTNode<T> *& p)
{
if(p == NULL)
return -1;
int h1 = depth(p->Lchild);
int h2 = depth(p->Rchild);
if(h1>h2)return (h1+1);
return h2+1;
}
//***********************************************************************************
//二叉树消毁操作
template<class T>
BTNode<T>* destroy(BTNode<T>* p) //消毁函数，用来消毁二叉树中各个结点
{
if(p)
{
return destroy(p->Lchild);
return destroy(p->Rchild);
delete p;
}
}
//********************************************************************************
//主函数设计
int main ()
{
BTNode<int> * rootNode = NULL;
int choiced = 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)
return 0;
else if(choiced == 1)
{
system("cls");
cout<<"请输入每个结点，回车确定，并以-1结束：\n";
createBinTree(rootNode );
}
else if(choiced == 2)
{
system("cls");
cout<<"先序遍历二叉树结果：\n";
preOrder(rootNode);
cout<<endl;
system("pause");
}
else if(choiced == 3)
{
system("cls");
cout<<"中序遍历二叉树结果：\n";
inOrder(rootNode);
cout<<endl;
system("pause");
}
else if(choiced == 4)
{
system("cls");
cout<<"后序遍历二叉树结果：\n";
levelOrder(rootNode);
cout<<endl;
system("pause");
}
else if(choiced == 5)
{
system("cls");
int count = countNode(rootNode);
cout<<"二叉树中结点总数为"<<count<<endl;
system("pause");
}
else if(choiced == 6)
{
system("cls");
int dep = depth(rootNode);
cout<<"此二叉树深度为"<<dep<<endl;
system("pause");
}
else if(choiced == 7)
{
system("cls");
cout<<"二叉树已被消毁！\n";
destroy(rootNode);
cout<<endl;
system("pause");
}
else
{
system("cls");
cout<<"\n\n\n\n\n\t错误选择！\n";
}
}
}
3.调试分析
3.1调试中问题
创建二叉树：依次输入二叉树前序遍历序列，构建对应二叉树。 
二叉树遍历：递归算法、非递归算法测试，调用对应函数进行测试，结果正确。 求二叉树深度和结点数：创建一个二叉树，调用相关函数，测试结果正确。 计算每层结点数：调用levelNum()函数，测试结果正确。  
调试时碰到很多问题，其中最关键问题是死循环问题，在非递归遍历时，轻易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利处理各个难题。

4.测试结果
（1）初始界面:主界面所包含内容

图4.1初始界面图

（2）运行结果：进行操作1，输入每个结点，显示结果以下

图4.2创建二叉树
进行操作2，实施结果以下：

图4.3二叉树先序遍历
进行操作3，实施结果以下：

图4.4二叉树中序遍历
进行操作4，实施结果以下：

图4.5二叉树后序遍历:
进行操作5，实施结果以下：

图4.6统计二叉树节点

进行操作6，实施结果以下：

图4.7查看树深度
总结
要能很好掌握编程,仅仅经过多个简单程序编写时无法达成,更需要大量积累和深入才可能经过此次课程设计。相关一个课题全部知识不仅仅是在书本上，多查阅部分资料能够愈加好完成课题，这就需要一个能力，即自学能力。此次课程设计还让我认识到自己缺点。此次选课题是二叉树遍历，因为本学期所学就是二叉树等数据结构，所以认为比较适合。刚开始认为会很简单，但到以后就出现部分难以处理问题，就像老师请教，并查阅相关资料。经过慢慢调试，最终测试成功。 
这次课程设计让我所学到数据结构知识发挥淋漓尽致，而且还拓展了我知识面，使我愈加熟练掌握多种方法。 
总而言之，这次课程设计增强了我自学能力，拓展了我知识面，让我对数据结构愈加了解。

参考文件
[1] 严蔚敏 吴伟民 《数据结构(C语言版)》清华大学出版社， 9月

[2] 谭浩强《C程序设计(第三版)》清华大学出版社 1月