版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
1、数据结构(双语)项目文档报告递归、非递归两种算法遍历二叉树专 业: 计算机科学与技术 班 级: 指导教师: 苏亚光 姓 名: 学 号: 目 录一、设计思想.3页二、算法流程图4.页三、源代码10页四、运行结果. 15页五、遇到的问题及解决15页六、心得体会16页一、设计思想1. 递归遍历二叉树算法思想:1先序遍历:首先判断根结点是否为空,为空则停止遍历,不为空则将左子作为新的根结点重新进行上述判断,左子遍历结束后,再将右子作为根结点判断,直至结束。到达每一个结点时,打印该结点数据,即得先序遍历结果。若二叉树非空,则依次进行如下操作:(1)访问跟结点;(2)前序遍历左子树;(3)前序遍历右子树。
2、2. 中序遍历:首先判断该结点是否为空,为空则结束,不为空则将左子作为根结点再进行判断,打印左子,然后打印二叉树的根结点,最后再将右子作为参数进行判断,打印右子,直至结束。若二叉树非空,则依次进行如下操作:(1)中序遍历左子树;(2)访问根结点;(3)中序遍历右子树。3. 后续遍历:指针到达一个结点时,判断该结点是否为空,为空则停止遍历,不为空则将左子作为新的结点参数进行判断,打印左子。左子判断完成后,将右子作为结点参数传入判断,打印右子。左右子判断完成后打印根结点。若二叉树非空,则依次进行如下操作:(1)后序遍历左子树;(2)后序遍历右子树;(3)访问根结点。2. 非递归遍历二叉树算法思想:
3、1. 先序遍历:建立一个栈,当指针到达根结点时,打印根结点,判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈,将左子作为新的根结点进行判断,方法同上。若当前结点没有左子,则直接将右子打印,同时将右子作为新的根结点判断。若当前结点没有右子,则打印左子,同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子,则当前结点为叶子结点,此时将从栈中出栈一个元素,作为当前的根结点,打印结点元素,同时将当前结点同样按上述方法判断,依次进行。直至当前结点的左右子都为空,且栈为空时,遍历结束。2. 中序遍历:建立一个栈,当指针到达根结点时,把根结点压栈,判断根结点是否有左孩子。有左孩子
4、的话将左孩子,将新结点入栈,然后再将指针指向当前结点的左子,直至左子为空,弹栈一个元素,作为当前结点,打印该栈顶元素,将指针指向当前结点右子,将右子作为新的结点,结点入栈,再次进行上面的判断,直至当前结点右子也为空,则再出栈一个元素作为当前结点,一直到结束,使得当前结点右子为空,且栈空,遍历结束。3. 后续遍历:建立一个栈,然后定义一个tag,取值为0,1,0代表右子没有去过,1代表去过。初始时指针指向根结点,将根结点压栈,指针指向左子,则将左子作为当前结点,继续判断直至左孩子为null,设q=null,tag=1。然后取得栈顶元素,设为当前结点,判断当前结点的右孩子是否等于q,如果相等,则打
5、印当前结点,然后弹出当前结点,并且令q=当前结点的值。然后继续判断,直至右孩子不等于q,则将指针指向右孩子,把右孩子设为当前结点,令tag=0,继续步骤,直到全部元素弹栈,栈为空时,遍历结束。二、 算法流程图开始判断结点是否为空null访问根结点结束先序方式遍历左子树先序方式遍历右子树是否 图1.先序递归流程图开始判断结点是否空按中序方式遍历左子树结束访问根结点按中根遍历方式遍历右子树yn图2. 中序递归流程图开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点yn图3 .后序递归流程图开始申请一个栈stack判断结点是否空输出结点值,压栈,指针指向它的左孩子判断结
6、点是否空弹出栈顶元素,指向结点的右孩子结束判断栈或结点是否空nynyn图4 . 先序非递归流程图开始申请一个stack判断结点是否空把结点压栈,指针指向它的左孩子判断结点是否空弹栈,设为当前结点,打印结点值,指向右孩子结束判断栈或结点是否空nyynn图1. 流程图图2. 流程图图3. 流程图 图 5. 中序非递归流程图开始申请一个栈stack,用一个bool变量tag标记右孩子已被访问把当前结点压栈,p=p->lchild top+判断标志tag是否为1输出结点值p = s.pop()p= p->rchild结束nyynnyyn判断结点是否空判断栈或结点是否为空判断结点是否空 图
7、6. 后序非递归流程图三 、源代码下面给出的是实现递归和非递归遍历二叉树的算法程序的源代码(合并在一起):#include <stdio.h>#include <stdlib.h>#define max 100 /定义堆栈最大容量enum boolfalse,true;enum rvisitrchildnovisit,rchildvisit; /在后序遍历二叉树时用来指示是否已访问过右子树typedef struct bitnode /定义二叉树节点结构char data; /数据域 struct bitnode *lchild,*rchild; /左右孩子指针域bit
8、node,*bitree;typedef struct /定义堆栈结构bitree elemmax; /栈区 int top; /栈顶指针bitreestack;void initial(bitreestack &); /初始化一个堆栈bool push(bitreestack &,bitree); /将一个元素入栈bool pop(bitreestack&,bitree &); /将一个元素出栈bool gettop(bitreestack ,bitree &); /取得堆栈栈顶元素 bool stackempty(bitreestack); /判断堆
9、栈是否已空void createbitree(bitree &); /生成一个二叉树void preorder(bitree); /先序非递归遍历二叉树void inorder(bitree); /中序非递归遍历二叉树void postorder(bitree); /后序非递归遍历二叉树void pretravel(bitree ); /先序递归遍历二叉树void midtravel(bitree ); /中序递归遍历二叉树void posttravel(bitree ); /后序递归遍历二叉树int main() bitree t; int flag=1; /标记 bool temp
10、; printf("二叉树的递归和非递归遍历n"); createbitree(t); /生成一棵二叉树 printf ("n");printf("递归先序遍历二叉树: ");pretravel(t);printf("n"); printf ("n");printf("递归中序遍历二叉树: ");midtravel(t);printf("n");printf ("n");printf("递归后序遍历二叉树: ");p
11、osttravel(t);printf("nnn"); if(t) printf ("nn"); printf("非递归先序遍历二叉树: "); preorder(t); printf("n"); else printf("二叉树为空n"); if(t) printf("非递归中序遍历二叉树: "); inorder(t); printf("n"); else printf("二叉树为空n"); if(t) printf("非
12、递归后序遍历二叉树: "); postorder(t); printf("nnn"); else printf("二叉树为空n"); void initial(bitreestack &s)s.top=-1; /栈顶指针初始化为-1bool push(bitreestack &s,bitree ch) /将元素ch入栈,成功返回true,失败返回false if(s.top>=max-1) return false; /判断是否栈满 else s.top+; /栈顶指针top加一 s.elems.top=ch; /入栈 r
13、eturn true; bool pop(bitreestack &s,bitree &ch) /将栈顶元素出栈,成功返回true,并用ch返回该元素值,失败返回false if(s.top<=-1) return false; /判断是否栈空 else s.top-; /栈顶指针减一 ch=s.elems.top+1; return true; bool gettop(bitreestack s,bitree &ch) /取得栈顶元素,成功返回true,并用ch返回该元素值,失败返回false if(s.top<=-1) return false; els
14、e ch=s.elems.top; /显示栈顶元素 return true; bool stackempty(bitreestack s) /判断堆栈是否已空,若空返回true,不空返回false if(s.top<=-1) return true; else return false; void createbitree(bitree &t) /生成一棵二叉树,该二叉树以t为根结点 char ch; scanf("%c",&ch); /读入一个字符 if(ch=' ') t=null; else t=(bitnode *)malloc
15、(sizeof(bitnode); /生成一个新结点 t->data=ch; createbitree(t->lchild); /生成左子树 createbitree(t->rchild); /生成右子树 void pretravel(bitree t)/先序遍历if(t) printf("%c",t->data);pretravel(t->lchild);pretravel(t->rchild); void midtravel(bitree t)/中序遍历if(t) midtravel(t->lchild);printf(&quo
16、t;%c",t->data);midtravel(t->rchild); void posttravel(bitree t)/后序遍历if(t) posttravel(t->lchild);posttravel(t->rchild);printf("%c",t->data); void preorder(bitree t) /先序非递归遍历以t为根结点的二叉树 bitreestack s; bitree p; initial(s); p=t; while(p|!stackempty(s) if(p) printf("%c&q
17、uot;,p->data); push(s,p); p=p->lchild; else pop(s,p); p=p->rchild; printf("n"); void inorder(bitree t) /中序非递归遍历以t为根结点的二叉树 bitreestack s; bitree p; initial(s); p=t; while(p|!stackempty(s) if(p) push(s,p); p=p->lchild; else pop(s,p); printf("%c",p->data); p=p->rch
18、ild; printf("n"); void postorder(bitree t) /后序非递归遍历以t为根结点的二叉树 bitreestack s; bitree p,q; rvisit tag; initial(s); p=t; do while(p) push(s,p); p=p->lchild; q=null; tag=rchildvisit; while(!stackempty(s)&&tag) gettop(s,p); if(p->rchild=q) printf("%c",p->data); pop(s,
19、p); q=p; else p=p->rchild; tag=rchildnovisit; while(!stackempty(s); printf("n");四 、运算结果例:输入:12空格空格34空格空格空格 即 :12 34 图7. 递归和非递归遍历二叉树结果图五、遇到的问题及解决这部分我主要遇到了如下两个问题,其内容与解决方法如下所列:问题1描述: 初步完成编程的工作时,在输入二叉树的发现只能输入一个字符,而且程序不再进行,最后是自己的不小心将语句char a; scanf("%c",&a);中的%c写为%d导致的。问题1解决方法:
20、将%d改为%c问题2描述:在构建二叉树的过程中,我最初用一重指针作为void create()的形参,导致创建的二叉树一直为空。后来经过深入思考,用二重指针实现了二叉树的构建。还有在编写主函数void main( )时,最初没有没有在函数体最后加上”getchar();”存储回车,导致调用创建函数构造二叉树时陷入莫名其妙的死循环。后来通过上网查阅资料,终于认识到错误所在。问题2解决方法: 用二重指针实现了二叉树的构建,在函数体最后加上”getchar();”存储回车。六 、心得体会课程设计期间,遇见一些问题,一个就是怎样后序非递归遍历二叉树,经过分析和斟酌,终于得到比较满意的程序,使得这个程序变得有一点意义。这一次的课程设计给我们提供了一个既能动手又动脑,独立实践的机会,应该紧紧抓住这个机会把所学的专业课程进一步的巩固和加深,进一步培养我们的综合能力。灵活运用各种数据类型组成
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 湖南农业大学《文献检索与专业英语》2023-2024学年第一学期期末试卷
- 我的家乡宁夏固原
- 重庆市万州区2023-2024学年高一历史上学期10月月考试题含解析
- 人教版道德与法治九年级上册第四单元第七课第一课时促进民族团结分层作业课件
- 山东省淄博市2023-2024学年高一上学期期末教学质量检测政治试题 含解析
- 2024至2030年中国冰淇淋机械行业投资前景及策略咨询研究报告
- 2024至2030年中国数码监视器行业投资前景及策略咨询研究报告
- 2024至2030年中国全自动二氧化氯发生器行业投资前景及策略咨询研究报告
- 2024至2030年中国甩棍行业投资前景及策略咨询研究报告
- 2024至2030年中国焊接结构用钢行业投资前景及策略咨询研究报告
- 声学实验设计:探索声音的传播与谐振现象
- 前庭性偏头痛课件
- 机动车交通安全统筹服务规范
- 贺州市钟山县2024年事业单位考试A类《职业能力倾向测验》统考试题含解析
- 外立面改造方案
- 沪教版五年级下册简易方程练习100题及答案
- 2024综合知识贵州事业单位刷题
- 《国库集中支付制度》课件
- 视频监控维保项目投标方案(技术标)
- 装配式混凝土预制构件项目市场研究报告
- 导游工作中的常见案例分析
评论
0/150
提交评论