算法与数据结构实验报告树及其应用.docx
- 文档编号:13277348
- 上传时间:2023-06-12
- 格式:DOCX
- 页数:24
- 大小:110.92KB
算法与数据结构实验报告树及其应用.docx
《算法与数据结构实验报告树及其应用.docx》由会员分享,可在线阅读,更多相关《算法与数据结构实验报告树及其应用.docx(24页珍藏版)》请在冰点文库上搜索。
算法与数据结构实验报告树及其应用
北京邮电大学软件学院
2019-2020学年第1学期实验报告
课程名称:
算法与数据结构课程设计
实验名称:
树及其应用
实验完成人:
日期:
2019年11月10日
一、实验目的
树是一种应用极为广泛的数据结构,也是这门课程的重点。
它们的特点在于非线性。
广义表本质上是树结构。
本章实验继续突出了数据结构加操作的程序设计观点,但根据这两种结构的非线性特点,将操作进一步集中在遍历操作上,因为遍历操作是其他众多操作的基础。
遍历逻辑的(或符号形式的)结构,访问动作可是任何操作。
本次实验希望帮助学生熟悉各种存储结构的特征,以及如何应用树结构解决具体问题(即原理与应用的结合)。
二、实验内容
必做内容
1)二叉树的建立与遍历
[问题描述]
建立一棵二叉树,并对其进行遍历(先序、中序、后序),打印输出遍历结果。
[基本要求]
从键盘接受输入(先序),以二叉链表作为存储结构,建立二叉树(以先序来建立),并采用递归算法对其进行遍历(先序、中序、后序),将遍历结果打印输出。
[测试数据]
ABCффDEфGффFффф(其中ф表示空格字符)则输出结果为
先序:
ABCDEGF
中序:
CBEGDFA
后序:
CGBFDBA
2)打印二叉树结构
[问题描述]
按凹入表形式横向打印二叉树结构,即二叉树的根在屏幕的最左边,二叉树的左子树在屏幕的下边,二叉树的右子树在屏幕的上边。
例如:
[测试数据]
由学生依据软件工程的测试技术自己确定。
注意测试边界数据,如空二叉树。
[实现提示]
(1)利用RDL遍历方法;
(2)利用结点的深度控制横向位置。
选做内容
采用非递归算法实现二叉树遍历。
三、实验环境
Windows下利用vs2019完成,语言c++
四、实验过程描述
首先构造Tree类,内含树的结构体BiTree,以及本实验所要用到的一些操作
typedefstructBiTNode
{
TElemTypedata;
intdegree,depth,level;//度,高度,高度差
structBiTNode*lchild,*rchild;/*左右孩子指针*/
}BiTNode,*BiTree;
实现相应功能:
1、二叉树的建立与遍历
构造二叉树:
前序构造,先赋值,然后递归构造左子树,递归构造右函数
BiTNode*Tree:
:
CreatBiTree(BiTreeT){
TElemTypech;
cin>>noskipws>>ch;//不跳过空格
if(ch=='')
T=NULL;//输入空格表示空子树
else{
T=newBiTNode;//分配空间
if(!
T)//分配失败就退出
thrownewstd:
:
bad_alloc;
T->degree=0;//记录度
(T)->data=ch;
T->depth++;//度增加
T->lchild=CreatBiTree(T->lchild);//递归创建左子树
T->rchild=CreatBiTree(T->rchild);//递归创建右子树
if(T->lchild!
=NULL)
T->degree++;//有一个孩子度就加一
if(T->rchild!
=NULL)
T->degree++;
}
returnT;
}
销毁二叉树:
后序递归销毁左右子树(需要先查找到子树,销毁再销毁父亲树)
voidTree:
:
Release(BiTreeT){
if(T!
=NULL){
Release(T->lchild);//递归销毁左子树
Release(T->rchild);//递归销毁右子树
deleteT;
}
}
//前序遍历
voidTree:
:
PreOrderTraverse(BiTreeT,void(Tree:
:
*Visit)(BiTree)){
if(T)/*T不空*/
{
(this->*Visit)(T);/*先访问根结点*/
PreOrderTraverse(T->lchild,Visit);/*再先序遍历左子树*/
PreOrderTraverse(T->rchild,Visit);/*最后先序遍历右子树*/
}
}
//中序遍历
voidTree:
:
InOrderTraverse(BiTreeT,void(Tree:
:
*Visit)(BiTree))
{
if(T)
{
InOrderTraverse(T->lchild,Visit);/*先中序遍历左子树*/
(this->*Visit)(T);/*再访问根结点*/
InOrderTraverse(T->rchild,Visit);/*最后中序遍历右子树*/
}
}
//后序遍历
voidTree:
:
PostOrderTraverse(BiTreeT,void(Tree:
:
*Visit)(BiTree))
{
if(T)
{
PostOrderTraverse(T->lchild,Visit);/*先中序遍历左子树*/
PostOrderTraverse(T->rchild,Visit);/*最后中序遍历右子树*/
(this->*Visit)(T);/*再访问根结点*/
}
}
//查找深度
intTree:
:
TreeDepth(BiTreeT){
inti,j;
if(!
T)
return0;/*空树深度为0*/
if(T->lchild)
i=TreeDepth(T->lchild);/*i为左子树的深度*/
else
i=0;
if(T->rchild)
j=TreeDepth(T->rchild);/*j为右子树的深度*/
else
j=0;
T->depth=i>j?
i+1:
j+1;
returnT->depth;
}
//得到层数
voidTree:
:
getLevel(BiTreeT,intlevel){
if(T)
{
T->level=level;
getLevel(T->lchild,level+1);//得到左子树的层数,左子树根节点的层数比此节点多一
getLevel(T->rchild,level+1);//得到右子树的层数,右子树根节点的层数比此节点多一
}
}
//非递归中序遍历
voidTree:
:
NoRecInOrderTraverse(BiTreeT,void(Tree:
:
*Visit)(BiTree)){
LinkedStack
BiTreep=T;
while(p||!
S.isEmpty()){
if(p){
S.Push(p);//当节点不为空时就压栈,然后判断左孩子
p=p->lchild;
}
else{
p=S.Pop();//返回到父节点
(this->*Visit)(p);//访问
p=p->rchild;//然后指向右节点
}
}
}
实验二:
2、打印二叉树结构
//中序遍历RDL
voidTree:
:
InOrderTraverseRDL(BiTreeT,void(Tree:
:
*Visit)(BiTree))
{
if(T)
{
InOrderTraverseRDL(T->rchild,Visit);/*先中序遍历左子树*/
(this->*Visit)(T);/*再访问根结点*/
InOrderTraverseRDL(T->lchild,Visit);/*最后中序遍历右子树*/
}
}
//打印二叉树图形
打印图形时,需要中序遍历RDL(先遍历右节点,再遍历右节点)。
每一个字符占一行,所在的列根据此节点的层数来确定。
(
voidprintT(BiTreeT){//打印二叉树图形
for(inti=0;i
cout<<"";
}
cout< } 实验3: 采用非递归算法实现二叉树遍历 利用栈来模拟操作系统调用函数 判断该节点是否为空,如果不为空就压栈,否则弹出栈中最上层元素 //非递归前序遍历 voidTree: : NoRecPreOrderTraverse(BiTreeT,void(Tree: : *Visit)(BiTree)){ LinkedStack BiTreep=T; while(p||! S.isEmpty()){ if(p){ (this->*Visit)(p);//先访问 S.Push(p); p=p->lchild;//当节点不为空时就压栈,然后判断左孩子 } else{//节点为空时 p=S.Pop();//返回到父节点然后指向右节点 p=p->rchild; } } } //非递归后序遍历 后序遍历时如果当前结点左右子树均为空,则可以访问当前结点,或者左右子树不均为空,但是前一个访问的结点是当前结点的左孩子或者右孩子,则也可以访问当前结点 否则则压入栈中。 压栈时先压右节点再压左节点。 voidTree: : NoRecPostOrderTraverse(BiTreeT,void(Tree: : *Visit)(BiTree)){ LinkedStack S.Push(T);//将根节点压栈 BiTreepre=NULL;//前一个节点 BiTreecur;//现在的节点 while(! S.isEmpty())//如果栈不为空就一直进行 { cur=S.Peek();//观测现在的节点,不弹出 if((cur->lchild==NULL&&cur->rchild==NULL)//左右子树不均为空 ||(pre! =NULL&&(pre==cur->rchild||pre==cur->lchild)))//或前一个访问的结点是当前结点的左孩子或者右孩子,则可以访问 { (this->*Visit)(cur); cur=S.Pop();//弹出此节点 pre=cur;//改变现在的pre } else{ if(cur->rchild! =NULL) { S.Push(cur->rchild);//如果右孩子不为空就压入栈 } if(cur->lchild! =NULL) { S.Push(cur->lchild);//如果左孩子不为空就压入栈 } } } } voidvisitT(BiTreeT){//输出节点上的字符数据 cout< } 五、实验结果: 输入两组树,分别进行相关运算,得到如下结果: 六、源代码: LinkedStack.h 栈的模板类 #pragmaonce #include template structNode{ Tdata; Node }; template classLinkedStack { private: Node public: LinkedStack(); ~LinkedStack(); voidPush(T); TPop(); TPeek(); boolisEmpty(); }; template LinkedStack : LinkedStack(){ top=nullptr; } template LinkedStack : ~LinkedStack(){ Node while(top) { p=top; top=top->next; deletep; } } template voidLinkedStack : Push(Te){ Node p->data=e; p->next=top; top=p; } template TLinkedStack : Pop(){ if(! top) throw-1;//如果为空则失败 Node Te=p->data; top=top->next; deletep; p=NULL; returne; } template TLinkedStack : Peek(){ if(! top) throw-1;//如果为空则失败 Te=top->data; returne; } template boolLinkedStack : isEmpty(){ returntop==nullptr; } Tree.h #pragmaonce #include #include #include"LinkedStack.h" usingnamespacestd; typedefcharTElemType; typedefintStatus;/*Status是函数的类型,其值是函数结果状态代码,如OK等*/ typedefintBoolean;/*Boolean是布尔类型,其值是TRUE或FALSE*/ typedefstructBiTNode { TElemTypedata; intdegree,depth,level;//度,高度,高度差 structBiTNode*lchild,*rchild;/*左右孩子指针*/ }BiTNode,*BiTree; classTree { private: BiTreeroot; introotDepth; BiTNode*CreatBiTree(BiTreeT);//构造二叉树 voidRelease(BiTreeT);//销毁二叉树 voidInOrderTraverse(BiTree,void(Tree: : *Visit)(BiTree));//中序遍历 voidInOrderTraverseRDL(BiTree,void(Tree: : *Visit)(BiTree));//RDL中序遍历 voidPostOrderTraverse(BiTree,void(Tree: : *Visit)(BiTree));//后序遍历 voidPreOrderTraverse(BiTree,void(Tree: : *Visit)(BiTree));//前序遍历 intTreeDepth(BiTreeT);//测量树的深度 voidgetLevel(BiTree,int);//测量树的层数(节点所在层数) voidNoRecPreOrderTraverse(BiTree,void(Tree: : *Visit)(BiTree));//非递归前序遍历 voidNoRecInOrderTraverse(BiTree,void(Tree: : *Visit)(BiTree));//非递归中序遍历 voidNoRecPostOrderTraverse(BiTree,void(Tree: : *Visit)(BiTree));//非递归后序遍历 public: Tree(){//构造函数,调用CreatBiTree() root=NULL; root=CreatBiTree(root); rootDepth=TreeDepth(root); getLevel(root,1); } ~Tree(){//析构函数 Release(root); } voidvisitT(BiTreeT){//输出节点上的字符数据 cout< } voidprintT(BiTreeT){//打印二叉树图形 for(inti=0;i cout<<""; } cout< } //下面的几个函数是为了给外部调用而设计的 voidPreOrderTraverse(void(Tree: : *Visit)(BiTree)){ PreOrderTraverse(root,Visit); } voidInOrderTraverse(void(Tree: : *Visit)(BiTree)){ InOrderTraverse(root,Visit); } voidInOrderTraverseRDL(void(Tree: : *Visit)(BiTree)){ InOrderTraverseRDL(root,Visit); } voidPostOrderTraverse(void(Tree: : *Visit)(BiTree)){ PostOrderTraverse(root,Visit); } voidNoRecPreOrderTraverse(void(Tree: : *Visit)(BiTree)){ NoRecPreOrderTraverse(root,Visit); } voidNoRecInOrderTraverse(void(Tree: : *Visit)(BiTree)){ NoRecInOrderTraverse(root,Visit); } voidNoRecPostOrderTraverse(void(Tree: : *Visit)(BiTree)){ NoRecPostOrderTraverse(root,Visit); } }; Tree.cpp #include"Tree.h" //构造二叉树 BiTNode*Tree: : CreatBiTree(BiTreeT){ TElemTypech; cin>>noskipws>>ch;//不跳过空格 if(ch=='') T=NULL;//输入空格表示空子树 else{ T=newBiTNode;//分配空间 if(! T)//分配失败就退出 thrownewstd: : bad_alloc; T->degree=0;//记录度 (T)->data=ch; T->depth++;//度增加 T->lchild=CreatBiTree(T->lchild);//递归创建左子树 T->rchild=CreatBiTree(T->rchild);//递归创建右子树 if(T->lchild! =NULL) T->degree++;//有一个孩子度就加一 if(T->rchild! =NULL) T->degree++; } returnT; } //销毁二叉树 voidTree: : Release(BiTreeT){ if(T! =NULL){ Release(T->lchild);//递归销毁左子树 Release(T->rchild);//递归销毁右子树 deleteT; } } //前序遍历 voidTree: : PreOrderTraverse(BiTreeT,void(Tree: : *Visit)(BiTree)){ if(T)/*T不空*/ { (this->*Visit)(T);/*先访问根结点*/ PreOrderTraverse(T->lchild,Visit);/*再先序遍历左子树*/ PreOrderTraverse(T->rchild,Visit);/*最后先序遍历右子树*/ } } //中序遍历 voidTree: : InOrderTraverse(BiTreeT,void(Tree: : *Visit)(BiTree)) { if(T) { InOrderTraverse(T->lchild,Visit);/*先中序遍历左子树*/ (this->*Visit)(T);/*再访问根结点*/ InOrderTraverse(T->rchild,Visit);/*最后中序遍历右子树*/ } } //中序遍历RDL voidTree: : InOrderTraverseRDL(BiTreeT,void(Tree: : *Visit)(BiTree)) { if(T) { InOrderTraverseRDL(T->rchild,Visit);/*先中序遍历左子树*/ (this->*Visit)(T);/*再访问根结点*/ InOrderTraverseRDL(T->lchild,Visit);/*最后中序遍历右子树*/ } } //后序遍历 voidTree: : PostOrderTraverse(BiTreeT,void(Tree: : *Visit)(BiTree)) { if(T) { PostOrderTraverse(T->lchild,Visi
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 数据结构 实验 报告 及其 应用