数据结构课程设计二叉树遍历C++语言Word文档下载推荐.docx
- 文档编号:6624212
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:38
- 大小:118.95KB
数据结构课程设计二叉树遍历C++语言Word文档下载推荐.docx
《数据结构课程设计二叉树遍历C++语言Word文档下载推荐.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计二叉树遍历C++语言Word文档下载推荐.docx(38页珍藏版)》请在冰点文库上搜索。
根据数据建立二叉树,实现二叉树的中序、前序、后序遍历
2)模块:
栈的应用,队列结构的应用,二叉树的操作
问题4:
课题在实现过程中遇到的主要难点有哪些?
遍历二叉树过程中栈结构以及队列的使用
问题5:
课题中未能实现的功能有哪些?
以树形结构输出完全二叉树
记录人:
寇海洲2012年12月28日
1需求分析
1.1二叉树与树结构
树结构的是建立在数据逻辑结构基础上的数据结构类型,二叉树则是树结构中最常见和使用最多的类型。
通过对二叉树的操作,可以实现多种数据操作,如排序、查找等。
一个好的二叉树遍历算法应包含以下功能:
1)以递归和非递归方法建立二叉树或完全二叉树;
2)实现二叉树的前序遍历、中序遍历、后序遍历;
3)每种遍历算法皆以递归和非递归方法实现;
4)在具体实现时应用其他数据结构类型对数据进行操作,如:
栈,队列,数组。
1.2面向对象的程序设计
在面向对象的程序设计中,模板的使用很普遍,因此,如何在程序设计中使用模板使得方法的实现与定义分开,程序模块化,既方便了程序设计者,又为程序的后期维护带来便利。
1.3二叉树遍历的应用
当数据以数组或文档形式存储在内存时,其数据之间虽有逻辑联系,却过于分散,因此,建立二叉树以存储数据并且遍历该二叉树,可以从逻辑上理顺数据之间的关系,使得原本分数的数据排列的有序且可靠。
一个好的二叉树应用算法其空间复杂度与时间复杂度必然最低,这样给程序带来时间和空间上的极大优化。
1.4软件运行环境:
VisualC++6.0版本
2概要设计
2.1总体功能结构
二叉树的遍历,主要包含以下功能:
1)建立二叉树:
递归方法、非递归方法
2)中序遍历:
3)前序遍历:
4)后序遍历:
5)栈结构使用:
遍历时输入临时变量以保存
6)队列结构使用:
完全二叉树遍历时用以存储数据
2.2数据结构部分设计
2.2.1结点结构
二叉树结点结构中包数据域(data),指针域(*leftChild,*rightChild)。
结点结构的代码如下:
structBinTreeNode{//树结点
Tdata;
BinTreeNode<
T>
*leftChild;
*rightChild;
BinTreeNode():
leftChild(NULL),rightChild(NULL){}
BinTreeNode(Tx,BinTreeNode<
*l=NULL,BinTreeNode<
*r=NULL)
:
leftChild(l),rightChild(r){
data=x;
}
栈结构结点包含数据域(data),指针域(*link),实现代码如下:
structStackNode{//栈结点
Tdata;
StackNode<
*link;
StackNode(Td=0,StackNode<
*next=NULL):
link(next),data(d){}
};
队列结构结点包含数据域(data),指针域(*link),实现代码如下:
structLinkNode{
LinkNode<
LinkNode(LinkNode<
*ptr=NULL){
link=ptr;
}
LinkNode(constT&
item,LinkNode<
*ptr=NULL){
data=item;
2.2.2二叉树结构
二叉树包含了递归、非递归建树过程,递归、非递归的前序遍历、中序遍历、后续遍历过程。
二叉树的类定义包含各种操作,实现代码如下:
template<
typenameT>
classBinaryTree{//二叉树类定义
public:
BinaryTree():
root(NULL){}
BinaryTree(Tvalue):
root(NULL){
RefValue=value;
BinaryTree(BinaryTree<
&
s){
if(this!
=&
root=Copy(s.root);
}
~BinaryTree(){
destroy(root);
BinTreeNode<
*Parent(BinTreeNode<
*t){
return(root==NULL||root==t)?
NULL:
Parent(root,t);
*LeftChild(BinTreeNode<
return(t!
=NULL)?
t->
leftChild:
NULL;
*RightChild(BinTreeNode<
rightChild:
voidPreOrder(void(*visit)(BinTreeNode<
*t)){
PreOrder(root,visit);
voidInOrder(void(*visit)(BinTreeNode<
InOrder(root,visit);
voidPostOrder(void(*visit)(BinTreeNode<
PostOrder(root,visit);
}
voidCreateCompBinTree(T*CBT,intnum){//建立完全二叉树
CreateCompBinTree(CBT,num,0,root);
voidlevelOrder(void(*visit)(BinTreeNode<
*t));
//层次序遍历
voidPreOrder1(void(*visit)(BinTreeNode<
//非递归前序遍历
voidInOrder1(void(*visit)(BinTreeNode<
//非递归中序遍历
voidPostOrder1(void(*visit)(BinTreeNode<
//非递归后序遍历
friendistream&
operator>
>
(istream&
in,BinaryTree<
Tree){//输入二叉树
Tree.CreateBinTree(in,Tree.root);
returnin;
栈结构的定义中,包含了对数据的入栈、出栈、清空等基本操作,实现代码如下
classLinkedStack{
private:
StackNode<
*top;
LinkedStack():
top(NULL){}//无头结点
~LinkedStack(){
makeEmpty();
voidPush(constT&
x);
boolPop(T&
boolIsEmpty()const{
returntop==NULL;
boolIsFull()const{
returnfalse;
voidmakeEmpty();
friendostream&
operator<
<
(ostream&
os,LinkedStack<
s){
os<
"
StackSize:
"
s.getSize()<
endl;
*p=s.top;
inti=0;
while(p){
os<
++i<
:
p->
data<
p=p->
link;
returnos;
voidLinkedStack<
makeEmpty(){
*p;
while(top){
p=top;
top=top->
deletep;
}
队列的类定义,实现了对数据的入队、出队操作,实现代码如下:
classLinkedQueue{//无头结点
LinkedQueue(){
rear=NULL;
front=NULL;
~LinkedQueue(){
boolEnQueue(constT&
boolDeQueue(T&
returnfront==NULL;
os,LinkedQueue<
Q){
*p=Q.front;
inti=0;
os<
#"
<
++i<
p->
data<
endl;
p=p->
os<
QueueSize:
Q.getSize()<
voidoutput();
protected:
LinkNode<
*front,*rear;
3详细设计
3.1建立二叉树
3.1.1功能描述
二叉树是程序的核心,如何合理的建立至关重要。
本实例中使用递归和非递归方法分别建立二叉树,二叉树的数据来源于程序开始时建立的数组。
建立后的二叉树保存,并且留作之后的遍历使用。
3.1.2算法原理
本实例使用的是完全二叉树,首先建立头结点,并且保存数据,然后根据递归方法,分别建立其左右孩子结点,且左右孩子结点的指针域指向空。
3.1.3具体程序
以递归方式建立二叉树,每次建立一个结点后,将其左右孩子指针域置空,成为叶子结点。
具体实现代码如下:
voidBinaryTree<
CreateBinTree(istream&
in,BinTreeNode<
*&
subTree){
Titem;
if(in>
item){
if(item!
=RefValue){
subTree=newBinTreeNode<
(item);
//CreateRoot
assert(subTree);
CreateBinTree(in,subTree->
leftChild);
//Createleftchildtree
rightChild);
//Createreghtchildtree
else
{
subTree=NULL;
//建立完全二叉树
template<
CreateCompBinTree(T*CBT,intnum,intrt,BinTreeNode<
if(rt>
=num){
subTree=NULL;
else{
subTree=newBinTreeNode<
(CBT[rt]);
CreateCompBinTree(CBT,num,2*rt+1,subTree->
CreateCompBinTree(CBT,num,2*rt+2,subTree->
3.2前序遍历
3.2.1功能原理
通过前序遍历,将二叉树中的数据按照前序遍历的结果输出,达到前序便利的目的,方便数据的使用。
3.2.2算法原理
前序遍历使用了递归与非递归两种方法,在程序头文件中定义了两个函数分别实现其功能。
递归时,输出第一个结点数据时,找到数据,然后找到其后面的数据,然后依次递归输出。
非递归时,使用栈和队列结构,将部分数据保存在栈或队列中,等待将数据放到合适位置。
3.2.3具体程序
1)递归算法实现:
PreOrder(BinTreeNode<
*subTree,void(*visit)(BinTreeNode<
if(subTree!
=NULL){
visit(subTree);
PreOrder(subTree->
leftChild,visit);
rightChild,visit);
2)非递归算法实现:
PreOrder1(void(*visit)(BinTreeNode<
*t)){
LinkedStack<
BinTreeNode<
*>
S;
*p=root;
S.Push(NULL);
while(p!
=NULL){
visit(p);
//访问结点
if(p->
rightChild!
=NULL)
S.Push(p->
//预留右指针在栈中
leftChild!
=NULL)
leftChild;
//进左子树
elseS.Pop(p);
//左子树为空,由堆栈弹出
3.3中序遍历
3.3.1功能原理
通过中序遍历,将二叉树中的数据按照中序序遍历的结果输出,达到中序遍历的目的,实现数据的最优,方便数据的使用。
3.3.2算法原理
中序遍历使用了递归与非递归两种方法,在程序头文件中定义了两个函数分别实现其功能。
递归时,输出第一个结点数据时,找到数据,然后依次找到其后面的数据,然后依次递归输出。
非递归时,使用栈和队列结构,将部分数据保存在栈与队列中,等待将数据放到合适位置。
3.3.3具体程序
InOrder(BinTreeNode<
*subTree,void(*visit)(BinTreeNode<
if(subTree!
InOrder(subTree->
voidBinaryTree<
InOrder1(void(*visit)(BinTreeNode<
*t)){//非递归中序遍历
while(p!
=NULL||!
S.IsEmpty()){
while(p!
=NULL){//遍历指针向左下移动
S.Push(p);
//该子树沿途结点进栈
if(!
S.IsEmpty()){//栈不空时退栈
S.Pop(p);
visit(p);
//退栈,访问
rightChild;
//遍历指针进到右子女
3.4后序遍历
3.4.1功能原理
通过后序遍历,将二叉树中的数据按照后序遍历的结果输出,达到后序遍历的目的,实现数据的最优,方便数据的使用。
3.4.2算法原理
后序遍历使用了递归与非递归两种方法,在程序头文件中定义了两个函数分别实现其功能。
3.4.3具体程序
PostOrder(BinTreeNode<
=NULL){
PostOrder(subTree->
visit(subTree);
}2)非递归算法实现:
PostOrder1(void(*visit)(BinTreeNode<
stkNode<
>
stkNode<
w;
*p=root;
//p是遍历指针
do{
while(p!
=NULL){
w.ptr=p;
w.tag=stkNode<
L;
//枚举类型定义在structstkNode中,如定义为全局性就简单了
S.Push(w);
intcontinue1=1;
while(continue1&
&
!
S.IsEmpty()){
S.Pop(w);
p=w.ptr;
switch(w.tag){//判断栈顶的tag标记
casestkNode<
L:
w.tag=stkNode<
R;
S.Push(w);
continue1=0;
p=p->
break;
casestkNode<
R:
}
}while(!
S.IsEmpty());
//继续遍历其他结点
cout<
3.5层次序非递归遍历
3.5.1功能原理
层次序非递归遍历,依据的是递归原理,每次遍历一个结点后,同时让其左右孩子入队,以便达到层次序的目的。
3.5.2算法原理
每次遍历完一个结点后,检查该结点是否为叶子结点,如果是叶子结点则继续下一结点的遍历,否则其左右孩子入队,继续遍历。
3.5.3具体程序
levelOrder(void(*visit)(BinTreeNode<
*t)){//层次序遍历
if(root==NULL)return;
LinkedQueue<
*>
Q;
visit(p);
Q.EnQueue(p);
while(!
Q.IsEmpty()){
Q.DeQueue(p);
if(p->
=NULL){
visit(p->
Q.EnQueue(p->
Q.EnQueue(p->
3.6栈结构
3.6.1功能原理
运用栈结构,在非递归算法中,未输出的数据暂时存入栈中,依据先进后出原则,方便了二叉树的遍历。
3.6.2算法原理
二叉树的结点信息,保存在栈中。
第一个入栈的数据元素保存在栈底,后进栈的在上方,现出栈。
3.6.3具体程序
Push(constT&
x){
top=newStackNode<
(x
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 二叉 遍历 C+ 语言