有关树与二叉树的算法.docx
- 文档编号:14225223
- 上传时间:2023-06-21
- 格式:DOCX
- 页数:20
- 大小:176.41KB
有关树与二叉树的算法.docx
《有关树与二叉树的算法.docx》由会员分享,可在线阅读,更多相关《有关树与二叉树的算法.docx(20页珍藏版)》请在冰点文库上搜索。
有关树与二叉树的算法
湖南农业大学
综合设计报告
学生姓名:
张佳娜
学号:
200940204101
年级专业:
2009信息与计算科学
指导老师:
刘凯讲师
学院:
理学院
湖南·长沙(小三号黑体)
提交日期:
2010年12月
1设计题目
实现树与二叉树的转换的实现。
以及树的前序、后序递归、非递归算法,层次序的非递归算法的实现,应包含建树的实现
2设计目的、要求
通过课程设计,巩固所学的理论知识,培养综合运用所学知识解决实际问题的能力。
能根据实际问题的具体情况,结合数据结构课程中的基本理论和基本算法,正确分析出数据的逻辑结构,合理选择相应的存储结构,并能设计出解决问题的有效办法。
3设计原理
对任意二叉树进行递归前序遍历和后序遍历,用栈实现非递归的前序遍历和后序遍历,还有对树的层次遍历和以及树与二叉树的转换。
4采用软件、设备
计算机,MicrosoftVisualC++6.0软件
5设计内容
(1)实现树与二叉树的转换的实现。
以及树的前序、后序的递归、非递归算法,层次序的非递归算法的实现,应包含建树的实现。
(2)详细步骤
二叉树创建
用链表现实创建一个树节点的结构体,从键盘输入数据,存入数组。
把下标为2*i+1的值存入左孩子,为2*i+2的存入右孩子btreenodecreat(),btreenodestree_creat(char*a,int)
.
二叉树前序递归算法
若二叉树为空,则操作空;否则
(1)访问根节点;
(2)先序遍历左子树(3)先序遍历右子树。
Viodpreorder(btreenoderoot)
二叉树后序遍历递归算法
若二叉树为空,则操作空;否则
(1)后序遍历左子树;
(2)后序遍历右子树;(3)访问根节点;voidpostorder(btreenoderoot)
.
前序非递归遍历算法
Btreenode根指针,若btreenode!
=NULL对于非递归算法引入栈模拟递归工作栈,初始时栈为空。
VoidF_preorder(btreenoderoot)
后序非递归遍历算法
Btreenode是要遍历树的根指针,后续遍历要求在遍历完左右子树之后,再访问根。
需要判断根节点的左右子树是否都遍历过,voidF_postorder(btreenoderoot)
层次遍历递归算法
按照树的从左到右访问树的节点,层序遍历用于保存节点的容器是队列。
Voidlevelorder(btreenoderoot)
树与二叉树的转换算法
转换时节点的第一个孩子变为它的左孩子,兄弟节点变为它的右孩子。
Voidexchange(),classtree
.
各模块流程图
图1二叉树的创建
图2前序递归遍历
图3后序递归遍历
图4前序非递归遍历
图5后序非递归遍历
图6层序遍历
图7
6原始程序、数据
#include
usingnamespacestd;
#include
#include
#definemaxsize100
constintk=10;//=========================
#defineLENsizeof(structbtree)
intmax=1;
typedefstructbtree//二叉树节点结构体
{
btree*lchild,*rchild;
chardata;
}*btreenode;
structtree//=====================================
{
chardate;
tree*a[k];
};
typedefstructstackelemtype//栈的结构体
{
btreenodeptr;
intflag;
}stackelemtype;
btreenodep;
tree*q;
//二叉树的建立
btreenodestree_creat(char*a,intk)
{
btreenoderoot;
max++;
if(a[k]=='\0'||k>maxsize)
returnNULL;//判断树是否为空
else
{
root=(btreenode)malloc(LEN);//动态申请节点
root->data=a[k];
root->lchild=stree_creat(a,2*k+1);//递归调用为左孩子赋值
root->rchild=stree_creat(a,2*k+2);//递归调用为右孩子赋值
returnroot;//返回根节点指针
}
}
voidprint(btreenoderoot)//输出所创建的二叉树
{
btreenodeh[maxsize]={NULL};
inttop=0,base=0,j=0,k=0,n=0,m=0;
h[top]=root;
j=log(max+1)/log
(2)-1;
if(pow(2,j+1)-1 cout<<"你刚输入的: \n"; while(h[base]! =NULL)//把二叉树的值一次输入数组 { h[++top]=h[base]->lchild; h[++top]=h[base]->rchild; base++; } for(top=0;h[k]! =NULL;top++)//按层输出 { m=pow(2,j)-top;//计算每行输出的空格数 if(top! =0)m=m-top; for(n=0;n cout<<""; for(base=0;base =NULL;base++)//控制每层输出的个数 { if(h[k]->data=='0')cout<<"["<<"]";//当为空时输出[] elsecout< k++; } cout<<"\n"; for(n=0;n<(m-1);n++) cout<<""; for(base=0;base =NULL;base++) cout<<"/"<<"|"; cout<<"\n"; } } //二叉树的后续遍历递归算法 voidpostorder(btreenoderoot) { if(root==NULL)return;//递归调用的约束条件 else { postorder(root->lchild); postorder(root->rchild); if(root->data=='0'); else cout<<"["< } } //二叉树的前序遍历递归算法 voidpreorder(btreenoderoot) { if(root==NULL)return;//递归调用的约束条件 else { if(root->data=='0'); else cout<<"["< preorder(root->lchild); preorder(root->rchild); } } //二叉树的前序遍历非递归算法 voidF_preorder(btreenoderoot) { btreenodes[maxsize];//申请一个btreenode数组 inttop=0;//采用顺序栈,并假定不会发生上溢 do { while(root! =NULL)//当结点不为空时 { if(root->data=='0'); else cout<<"["< s[++top]=root;//依次将接点压入栈 root=root->lchild;//跟赋值为它的左孩子 } if(top>0)//节点为空但栈顶不为零时 { root=s[top--];//栈顶下移把栈顶元素赋给根节点 root=root->rchild;//跟赋值它为右孩子 } }while(root! =NULL||top>0); } //二叉树的后序遍历非递归算法 voidF_postreorder(btreenoderoot) { stackelemtypes[maxsize]; btreenodep=root; inttop=0; do { while(p! =NULL)//当结点不为空时 { s[top].flag=0;//标记位赋为零 s[top].ptr=p;//将树的节点依次压入栈中 p=p->lchild;//树沿左子树下移 top++; } while(s[top-1].flag==1)//当栈的做上面元素标记为一时输出 { if(s[top-1].ptr->data=='0')top--; else cout<<"["< } if(top>0)//当节点为空但栈顶不为零时 { s[top-1].flag=1;//栈的最上面元素标记位赋值为一 p=s[top-1].ptr;//栈的最上面元素树节点赋给p p=p->rchild;//树沿右子树下移 } }while(top>0); } //层次遍历 voidlevelorder(btreenoderoot) { btreenodes[maxsize];//申请一个btreenode数组 intmax,i=0; s[0]=root;//数组首元赋为根节点 while(root! =NULL)//当节点不为空时 { s[2*i+1]=root->lchild;//左孩子赋给下标为2*i+1的数组元 s[2*i+2]=root->rchild;//右孩子赋给下标为2*i+2的数组元 i++; root=s[i];//root变为当前数组元素的值 max=i; } for(i=0;i { if(s[i]->data=='0'); else cout<<"["< } } voidpause() { cout< system("pause"); cout< } //树转换成二叉树 voidexchange(tree*&H,btree*BH)//======================================= { H=newtree; for(inti=0;i { H->a[i]=NULL; } if(BH==NULL) { H=NULL; } else { H->date=BH->data; if(BH->lchild! =NULL) { exchange(H->a[0],BH->lchild); intj=1; btree*c=BH->lchild; while(c->rchild! =NULL) { c=c->rchild; exchange(H->a[j],c); j++; } } } } voidprinttree(tree*H) { if(H! =NULL) { cout< for(inti=0;i { printtree(H->a[i]); } } } btreenodecreat() { btreenodep=NULL; cout<<"请输入你的二叉树(按层次由上往下从左到右依次输入并按#结束,如果节点为空请输入'0'),输入为: \n"; inti=0,j=0; charb[maxsize]={'#'},n; //当输入'#'时给数组赋值 do { cin>>n; if(n! ='#')b[i]=n; i++; }while(n! ='#'); p=stree_creat(b,0);//创建树 print(p);//输出树 returnp; } //主函数 intmain() { intk; cout<<"\n"; cout<<"\n__________________________________________"; cout<<"|欢迎使用多种遍历器|"; cout<<"|树与二叉树的转换|"; cout<<"||"; cout<<"|___________________________________________|\n"; do { cout<<"\n"; cout<<"\n1.创建二叉树"; cout<<"\n2.前序遍历递归算法"; cout<<"\n3.后序遍历递归算法"; cout<<"\n4.前序非递归遍历算法"; cout<<"\n5.后序非递归遍历算法"; cout<<"\n6.层序非递归遍历算法"; cout<<"\n7.树与二叉树的转换"; cout<<"\n8.输出树"; cout<<"\n9.退出操作\n"; cout<<"请选择你要进行的操作(数字键): "; cin>>k; switch(k) { case1: { p=creat();//调用creat()创建二叉树 }break; case2: { cout<<"二叉树的前序递归遍历: "; preorder(p);//调用preorder()前序遍历 }break; case3: { cout<<"二叉树的后序递归遍历: "; postorder(p);//调用postorder()后续遍历 }break; case4: { cout<<"二叉树的前序非递归遍历: "; F_preorder(p);//调用F_preorder(p)前序遍历 }break; case5: { cout<<"二叉树的后序非递归遍历: "; F_postreorder(p);//调用F_postorder(p)后序遍历 }break; case6: { cout<<"二叉树的层次非递归递归遍历: "; levelorder(p); }break; case7: {btree*a; a=newbtree; a->data=0; a->lchild=p; a->rchild=NULL; exchange(q,a);//调用exchange()实现树与二叉树的转换 deletep; returnmain();//返回主函数 }break; case8: {printtree(q);} break; } }while(k>=0&&k<9); return0; } data<<"]";data<<"]";//依次输出
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 有关 二叉 算法
![提示](https://static.bingdoc.com/images/bang_tan.gif)