二叉树的遍历课程设计.docx
《二叉树的遍历课程设计.docx》由会员分享，可在线阅读，更多相关《二叉树的遍历课程设计.docx（18页珍藏版）》请在冰点文库上搜索。
二叉树的遍历课程设计
《数据结构》课程设计报告
设计题目：
二叉树的遍历
姓名：
陈雷
学号：
7
专业：
运算机科学与技术
院系：
运算机科学与技术
班级：
1002
指导教师：
吴克力
2012年3月1日
摘要：
本文主要说明如何实现二叉树的遍历。
这次二叉树的遍历基于二叉树的二叉链表存储结构。
遍历方式包括：
前序遍历，中序遍历，后续遍历，层序遍历。
其中前序遍历和后续遍历采用非递归算法实现。
编程环境为VC++，除遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，和最近一路先人（LCA）问题的算法。
关键字：
二叉树遍历非递归C++LCA
Abstract:
Thispapermainlydescribeshowtoimplementbinarytreetraversal.Thebinarytreetraversalisbasedonbinarytreebinarystoragestructure.Traversalmethodincludes:
preordertraversal,inordertraversal,postordertraversal,levelordertraversal.Theformerpreordertraversalandpostorderuseofnon-recursivealgorithm.ProgrammingenvironmentisVC++,inadditiontotraversaloperation,alsoincreasedforsolvingthebinarytreedepth、summarypointsandeachlayerofnodes,aswellasthemostrecentcommonancestor（LCA）algorithm.
Keywords:
binarytreetraversalnon-recursiveC++LCA
一、问题描述
问题描述：
创建二叉树并遍历
大体要求：
1、别离运用非递归的方式完成对二叉树的先序和后序遍历
2、输出二叉树的高度
3、输出每一层的结点数
4、查找结点P和结点Q的最近一路先人
二、需求分析
1．本程序的功能包括二叉树的成立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近一路先人，二叉树的打印。
2．程序运行后显现提示信息，等候用户输入0—6以进入相应的操作功能。
3．用户输入数据完毕，程序将输出运行结果。
4．测试数据应为字符型数据。
三、概要设计
1．创建二叉树
输入数据不低于15个，用递归方式成立二叉树。
2．二叉树的非递归前序遍历示用意
图二叉树前序遍历示用意
3．二叉树的后序非递归遍历示用意
图二叉树后序遍历示用意
四、数据结构设计
1．二叉树结点数据类型概念为：
template
structBiNode
{
BiNode*rchild,*lchild;//指向左右孩子的指针
Tdata;//结点数据信息
};
2．二叉树数据类型概念为：
template
classBiTree
{
template
friendostream&operator<<（ostream&os,BiTree&bt）;
public:
BiTree（）;//无参构造函数
BiTree（intm）{};//有参空构造函数
BiTree（Tary[],intnum,Tnone）;//有参构造函数
~BiTree（）;//析构函数
voidpreorder（）;//递归前序遍历
voidinorder（）;//递归中序遍历
voidpostorder（）;//递归后续遍历
voidlevelorder（）;//层序遍历
intcount（）;//计算二叉树的结点数
intdepth（）;//计算二叉树的深度
voiddisplay（ostream&os）;//打印二叉树，有层次
voidLevelNum（）;//计算每一层结点数
voidPreOrder（）;//非递归前序遍历
voidPostOrder（）;//非递归后序遍历
voidcreat（）;//创建二叉树
TleastCommanAncestor（Tva,Tvb）;//求树中任意两结点最近一路先人
protected:
//以下函数供上面函数挪用
//对应相同功能
voidcreat（BiNode*&root）;//创建
voidrelease（BiNode*&root）;//删除
BiNode*Build（Tary[],intnum,Tnone,intidx）;//用数组创建二叉树
voidPreOrder（BiNode*root）;//前序遍历
voidPostOrder（BiNode*root）;//后续遍历
voidLevelNum（BiNode*root）;//层序遍历
voidpreorder（BiNode*root）;//递归前序遍历
voidinorder（BiNode*root）;//递归中序遍历
voidpostorder（BiNode*root）;//递归后续遍历
voidlevelorder（BiNode*root）;//层序遍历
intcount（BiNode*root）;//计算结点数
intdepth（BiNode*root）;//计算深度
voiddisplay（ostream&os,BiNode*root,intdep）;//打印
staticboolleastCommanAncestor（BiNode*root,Tva,Tvb,BiNode*&result,BiNode*parrent）;//求最近一路先人
private:
BiNode*rootptr;
};
五、算法设计
一、创建二叉树
//实现外部递归挪用
voidBiTree:
:
creat（）
{
creat（rootptr）;
}
//类体内递归创建二叉树
template
voidBiTree:
:
creat（BiNode*&root）
{
Titem;
cin>>item;
if（item=='#'）root=NULL;
else
{
root=newBiNode;
root->data=item;
creat（root->lchild）;
creat（root->rchild）;
}
}
2、非递归前序遍历
template
voidBiTree:
:
PreOrder（）
{
PreOrder（rootptr）;
}
template
voidBiTree:
:
PreOrder（BiNode*root）
{
stack*>s;
while（root!
=NULL||!
（））
{
while（root）
{
cout<data;
（root）;
root=root->lchild;
}
if（!
（））
{
root=（）;
（）;
root=root->rchild;
}
}
}
3、非递归后序遍历
template
voidBiTree:
:
PostOrder（）
{
PostOrder（rootptr）;
}
template
voidBiTree:
:
PostOrder（BiNode*root）
{
stack*>s;//概念栈，节点类型为TreeNode
BiNode*p=root;
BiNode*pre=NULL;//pre表示最近一次访问的结点
while（p||!
（））
{
//沿着左孩子方向走到最左下。
while（p）
{
（p）;
p=p->lchild;
}
//getthetopelementofthestack
p=（）;
//若是p没有右孩子或其右孩子方才被访问过
if（p->rchild==NULL||p->rchild==pre）
{
//visitthiselementandthenpopit
cout<data;
（）;
pre=p;
p=NULL;
}
else
{
p=p->rchild;
}
}//endofwhile（p||（）!
=0）
}
4、求二叉树的高度
template
intBiTree:
:
depth（）
{
returndepth（rootptr）;
}
template
intBiTree:
:
depth（BiNode*root）
{
intrdep,ldep;
if（root==NULL）
return0;
else
{
ldep=depth（root->lchild）;
rdep=depth（root->rchild）;
return（rdep>ldep?
rdep:
ldep）+1;
}
}
5、求二叉树每一层的结点数
template
voidBiTree:
:
LevelNum（）
{
LevelNum（rootptr）;
}
template
voidBiTree:
:
LevelNum（BiNode*root）
{
queue*>q;
intfront,rear,first,last,level;
front=rear=first=0;
last=level=1;
if（root）
{
（root）;
rear++;
while（front{
root=（）;
（）;
front++;
if（root->lchild）
{
（root->lchild）;
rear++;
}
if（root->rchild）
{
（root->rchild）;
rear++;
}
if（front==last）
{
cout<<"第"<level++;
last=rear;
first=front;
}
}
}
}
6、求两节点最近一路先人
template
TBiTree:
:
leastCommanAncestor（Tn1,Tn2）{
returnleastCommanAncestor（rootptr,n1,n2）;
}
template
TBiTree:
:
leastCommanAncestor（BiNode*root,Tn1,Tn2）
{
if（root==NULL||root->data==n1||root->data==n2）
return-1;
if（（root->rchild!
=NULL）&&
（root->rchild->data==n1||root->rchild->data==n2））
returnroot->data;
if（（root->lchild!
=NULL）&&
（root->lchild->data==n1||root->lchild->data==n2））
returnroot->data;
if（root->data>n1&&root->datareturnroot->data;
if（root->data>n1&&root->data>n2）
returnleastCommanAncestor（root->lchild,n1,n2）;
if（root->datadatareturnleastCommanAncestor（root->rchild,n1,n2）;
}
6、算法流程图
六、程序测试与实现
一、函数之间的挪用关系
二、主程序
voidmain（）
{
BiTreeTree
（1）;
while
（1）{
cout<<"\t\t欢迎利用本系统！
！
"<cout<<"\t\t########################################"<cout<<"\t\t##"<cout<<"\t\t#1--创建一颗二叉树并显示#"<cout<<"\t\t#2--遍历二叉树#"<cout<<"\t\t#3--查询二叉树的深度和结点数#"<cout<<"\t\t#4--查询每层结点数#"<cout<<"\t\t#5--查找两节点P和Q的最近一路先人#"<cout<<"\t\t#6--退出#"<cout<<"\t\t##"<cout<<"\t\t########################################"<cout<<"请输入你的选择：
";
intx;
cin>>x;
switch（x）{
case1:
{
cout<<"请输入二叉树的前序遍历：
"<cout<<"（以#作为分支结尾，例如：
AB##C##）"<（）;
cout<cout<}break;
case2:
{
cout<cout<<"前序遍历为：
";
（）;
cout<cout<<"中序遍历为：
";
（）;
cout<cout<<"后序遍历为：
";
（）;
cout<cout<<"层序遍历为：
";
（）;
cout<cout<}break;
case3:
{
cout<<"树的深度为：
"<<（）<cout<<"树的结点数：
"<<（）<cout<}break;
case4:
{
（）;
}break;
case5:
{
charch1,ch2;
cout<<"请输入P数据信息：
";
cin>>ch1;
cout<<"请输入Q数据信息：
";
cin>>ch2;
cout<}break;
case6:
return;break;
default:
cout<<"请输入正确的选择！
！
！
"<}
}
}
3、测试数据
AB#CD###E#FGH##K###
4、测试结果
七、调试分析
创建二叉树：
依次输入二叉树前序遍历序列，构建相应的二叉树。
二叉树遍历：
递归算法、非递归算法测试，挪用相应函数进行测试，结果正确。
求二叉树深度和结点数：
创建一个二叉树，挪用相关函数，测试结果正确。
计算每层结点数：
挪用levelNum（）函数，测试结果正确。
求最近一路先人：
挪用LCA（）函数，测试结果正确。
八、碰到的问题及解决办法
调试时碰到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时，容易进入死循环，通过查找资料、分步伐试最终找到循环结束条件，顺利解决各个难题。
九、心得体会
通过本次课程设计，我发觉，有关一个课题的所有知识不单单是在讲义上，多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能力。
本次课程设计还让我熟悉到自己的缺点。
本次选的课题是二叉树的遍历，因为本学期所学的就是二叉树等数据结构，所以以为比较适合。
刚开始以为会很简单，但到后来就出现一些难以解决的问题，就像老师请教，并查阅相关资料。
通过慢慢的调试，最终测试成功。
这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我的知识面，使我加倍熟练的掌握各类方式。
总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据结构加倍了解。
十、参考文献
《C++程序设计》（第二版）吴乃陵况迎辉
《数据结构C++版》王红梅
升级会员 