数据结构课程设计二叉树遍历C++语言.docx
- 文档编号:4332375
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:38
- 大小:118.95KB
数据结构课程设计二叉树遍历C++语言.docx
《数据结构课程设计二叉树遍历C++语言.docx》由会员分享,可在线阅读,更多相关《数据结构课程设计二叉树遍历C++语言.docx(38页珍藏版)》请在冰点文库上搜索。
数据结构课程设计二叉树遍历C++语言
淮阴工学院实践报告
数据结构课程设计
设计题目:
二叉树遍历
系别:
计算机工程学院
专业:
软件工程
班级:
软件1111
学生姓名:
周淼学号:
1111315217
起止日期:
2012年12月24日~2012年12月30日
指导教师:
寇海洲
摘要:
现代社会生活中,计算机扮演着重要角色,而随着计算机运行速度的不断加快,对数据的处理能力也日益增强,因此,程序所涉及的数据成爆发式增长。
随之而来的问题就是如何科学有效的对数据进行操作,使得计算机的时间和空间利用率最高。
针对这样的问题,我选择了二叉树对数据的各种操作作为我的课程设计主题,希望通过课程设计来提高对数据的处理能力,促进对数据结构课程的理解,在日后面向对象的程序设计中科学的规划数据结构。
在本次课程设计中,二叉树的建立使用了递归算法,遍历则同时使用了递归与非递归的算法,同时,在遍历算法的实现中使用了栈结构与队列结构,这大大方便了二叉树的遍历。
在前序、中序、后续遍历算法中,分别实现了递归与非递归算法,从实际应用中体验了递归这一算法的优越性。
关键词:
二叉树建立,递归与非递归,遍历,栈,队列
编号:
47
淮阴工学院软件工程专业
数据结构课程设计答辩记录
课题名称:
二叉树的算法
班级软件1111学号1111315217姓名周淼
答辩记录
问题1:
课题中涉及到哪些数据结构和算法?
答:
1)数组,二叉树,栈,队列,线性表
2)二叉树的中序、前序、后序的递归、非递归遍历算法,层次序遍历非递归算法,栈、队列的实现算法
问题2:
课题研究和设计中的关键技术是什么?
答:
关键技术是二叉树的建立,以及栈结构、队列的算法实现
问题3:
课题的主要功能和模块有哪些?
答:
1)主要功能:
根据数据建立二叉树,实现二叉树的中序、前序、后序遍历
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
BinTreeNode
BinTreeNode():
leftChild(NULL),rightChild(NULL){}
BinTreeNode(Tx,BinTreeNode
:
leftChild(l),rightChild(r){
data=x;
}
栈结构结点包含数据域(data),指针域(*link),实现代码如下:
structStackNode{//栈结点
Tdata;
StackNode
StackNode(Td=0,StackNode
link(next),data(d){}
};
队列结构结点包含数据域(data),指针域(*link),实现代码如下:
structLinkNode{
Tdata;
LinkNode
LinkNode(LinkNode
link=ptr;
}
LinkNode(constT&item,LinkNode
data=item;link=ptr;
}
};
};
2.2.2二叉树结构
二叉树包含了递归、非递归建树过程,递归、非递归的前序遍历、中序遍历、后续遍历过程。
二叉树的类定义包含各种操作,实现代码如下:
template
public:
BinaryTree():
root(NULL){}
BinaryTree(Tvalue):
root(NULL){
RefValue=value;
}
BinaryTree(BinaryTree
if(this!
=&s){
root=Copy(s.root);
}
}
~BinaryTree(){
destroy(root);
}
BinTreeNode
return(root==NULL||root==t)?
NULL:
Parent(root,t);
}
BinTreeNode
return(t!
=NULL)?
t->leftChild:
NULL;
}
BinTreeNode
return(t!
=NULL)?
t->rightChild:
NULL;
}
voidPreOrder(void(*visit)(BinTreeNode
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
voidPreOrder1(void(*visit)(BinTreeNode
voidInOrder1(void(*visit)(BinTreeNode
voidPostOrder1(void(*visit)(BinTreeNode
friendistream&operator>>(istream&in,BinaryTree
Tree.CreateBinTree(in,Tree.root);
returnin;
}
栈结构的定义中,包含了对数据的入栈、出栈、清空等基本操作,实现代码如下
template
classLinkedStack{
private:
StackNode
public:
LinkedStack():
top(NULL){}//无头结点
~LinkedStack(){
makeEmpty();
}
voidPush(constT&x);
boolPop(T&x);
boolIsEmpty()const{
returntop==NULL;
}
boolIsFull()const{
returnfalse;
}
voidmakeEmpty();
friendostream&operator<<(ostream&os,LinkedStack
os<<"StackSize:
"< StackNode inti=0; while(p){ os<<++i<<": "< p=p->link; } returnos; } }; template voidLinkedStack : makeEmpty(){ StackNode while(top){ p=top; top=top->link; deletep; } } 队列的类定义,实现了对数据的入队、出队操作,实现代码如下: template public: LinkedQueue(){ rear=NULL; front=NULL; } ~LinkedQueue(){ makeEmpty(); } boolEnQueue(constT&x); boolDeQueue(T&x); voidmakeEmpty(); boolIsEmpty()const{ returnfront==NULL; } friendostream&operator<<(ostream&os,LinkedQueue LinkNode inti=0; while(p){ os<<"#"<<++i<<": "< p=p->link; } os<<"QueueSize: "< returnos; } voidoutput(); protected: LinkNode }; 3详细设计 3.1建立二叉树 3.1.1功能描述 二叉树是程序的核心,如何合理的建立至关重要。 本实例中使用递归和非递归方法分别建立二叉树,二叉树的数据来源于程序开始时建立的数组。 建立后的二叉树保存,并且留作之后的遍历使用。 3.1.2算法原理 本实例使用的是完全二叉树,首先建立头结点,并且保存数据,然后根据递归方法,分别建立其左右孩子结点,且左右孩子结点的指针域指向空。 3.1.3具体程序 以递归方式建立二叉树,每次建立一个结点后,将其左右孩子指针域置空,成为叶子结点。 具体实现代码如下: template : CreateBinTree(istream&in,BinTreeNode Titem; if(in>>item){ if(item! =RefValue){ subTree=newBinTreeNode assert(subTree); CreateBinTree(in,subTree->leftChild);//Createleftchildtree CreateBinTree(in,subTree->rightChild);//Createreghtchildtree } else { subTree=NULL; } } } //建立完全二叉树 template : CreateCompBinTree(T*CBT,intnum,intrt,BinTreeNode if(rt>=num){ subTree=NULL; } else{ subTree=newBinTreeNode } CreateCompBinTree(CBT,num,2*rt+1,subTree->leftChild); CreateCompBinTree(CBT,num,2*rt+2,subTree->rightChild); } } 3.2前序遍历 3.2.1功能原理 通过前序遍历,将二叉树中的数据按照前序遍历的结果输出,达到前序便利的目的,方便数据的使用。 3.2.2算法原理 前序遍历使用了递归与非递归两种方法,在程序头文件中定义了两个函数分别实现其功能。 递归时,输出第一个结点数据时,找到数据,然后找到其后面的数据,然后依次递归输出。 非递归时,使用栈和队列结构,将部分数据保存在栈或队列中,等待将数据放到合适位置。 3.2.3具体程序 1)递归算法实现: template : PreOrder(BinTreeNode if(subTree! =NULL){ visit(subTree); PreOrder(subTree->leftChild,visit); PreOrder(subTree->rightChild,visit); } } 2)非递归算法实现: template : PreOrder1(void(*visit)(BinTreeNode LinkedStack BinTreeNode S.Push(NULL); while(p! =NULL){ visit(p);//访问结点 if(p->rightChild! =NULL) S.Push(p->rightChild);//预留右指针在栈中 if(p->leftChild! =NULL) p=p->leftChild;//进左子树 elseS.Pop(p);//左子树为空,由堆栈弹出 } } 3.3中序遍历 3.3.1功能原理 通过中序遍历,将二叉树中的数据按照中序序遍历的结果输出,达到中序遍历的目的,实现数据的最优,方便数据的使用。 3.3.2算法原理 中序遍历使用了递归与非递归两种方法,在程序头文件中定义了两个函数分别实现其功能。 递归时,输出第一个结点数据时,找到数据,然后依次找到其后面的数据,然后依次递归输出。 非递归时,使用栈和队列结构,将部分数据保存在栈与队列中,等待将数据放到合适位置。 3.3.3具体程序 1)递归算法实现: template : InOrder(BinTreeNode if(subTree! =NULL){ InOrder(subTree->leftChild,visit); visit(subTree); InOrder(subTree->rightChild,visit); } } 2)非递归算法实现: template : InOrder1(void(*visit)(BinTreeNode LinkedStack BinTreeNode while(p! =NULL||! S.IsEmpty()){ while(p! =NULL){//遍历指针向左下移动 S.Push(p);//该子树沿途结点进栈 p=p->leftChild; } if(! S.IsEmpty()){//栈不空时退栈 S.Pop(p);visit(p);//退栈,访问 p=p->rightChild;//遍历指针进到右子女 } } } 3.4后序遍历 3.4.1功能原理 通过后序遍历,将二叉树中的数据按照后序遍历的结果输出,达到后序遍历的目的,实现数据的最优,方便数据的使用。 3.4.2算法原理 后序遍历使用了递归与非递归两种方法,在程序头文件中定义了两个函数分别实现其功能。 递归时,输出第一个结点数据时,找到数据,然后依次找到其后面的数据,然后依次递归输出。 非递归时,使用栈和队列结构,将部分数据保存在栈与队列中,等待将数据放到合适位置。 3.4.3具体程序 1)递归算法实现: template : PostOrder(BinTreeNode if(subTree! =NULL){ PostOrder(subTree->leftChild,visit); PostOrder(subTree->rightChild,visit); visit(subTree); } }2)非递归算法实现: template : PostOrder1(void(*visit)(BinTreeNode //非递归后序遍历 LinkedStack stkNode BinTreeNode do{ while(p! =NULL){ w.ptr=p; w.tag=stkNode : L; //枚举类型定义在structstkNode中,如定义为全局性就简单了 S.Push(w); p=p->leftChild; } 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->rightChild;break; casestkNode : R: visit(p);break; } } }while(! S.IsEmpty());//继续遍历其他结点 cout< } 3.5层次序非递归遍历 3.5.1功能原理 层次序非递归遍历,依据的是递归原理,每次遍历一个结点后,同时让其左右孩子入队,以便达到层次序的目的。 3.5.2算法原理 每次遍历完一个结点后,检查该结点是否为叶子结点,如果是叶子结点则继续下一结点的遍历,否则其左右孩子入队,继续遍历。 3.5.3具体程序 template : levelOrder(void(*visit)(BinTreeNode if(root==NULL)return; LinkedQueue BinTreeNode visit(p);Q.EnQueue(p); while(! Q.IsEmpty()){ Q.DeQueue(p); if(p->leftChild! =NULL){ visit(p->leftChild); Q.EnQueue(p->leftChild); } if(p->rightChild! =NULL){ visit(p->rightChild); Q.EnQueue(p->rightChild); } } } 3.6栈结构 3.6.1功能原理 运用栈结构,在非递归算法中,未输出的数据暂时存入栈中,依据先进后出原则,方便了二叉树的遍历。 3.6.2算法原理 二叉树的结点信息,保存在栈中。 第一个入栈的数据元素保存在栈底,后进栈的在上方,现出栈。 3.6.3具体程序 template voidLinkedStack : Push(constT&x){ top=newStackNode
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 二叉 遍历 C+ 语言