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

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

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

I

目录
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

17

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语言版)》清华大学出版社， 2009年9月

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