1 / 22
文档名称:

用递归非递归两种方法遍历二叉树.doc

格式:doc   大小:268KB   页数:22页
下载后只包含 1 个 DOC 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

用递归非递归两种方法遍历二叉树.doc

上传人:164922429 2020/2/3 文件大小:268 KB

下载得到文件列表

用递归非递归两种方法遍历二叉树.doc

文档介绍

文档介绍:数据结构(双语)——项目文档报告用递归、非递归两种方法遍历二叉树专业:计算机科学与技术班级:指导教师:姓名:学号:目录一、设计思想……………………………………………………….03二、算法流程图…………………………………………………….04三、源代码………………………………………………………….06四、运行结果……………………………………………………….12五、遇到的问题及解决…………………………………………….14六、心得体会……………………………………………………….15一、:(1)主函数main()主程序要包括:定义的二叉树T、建树函数、先序遍历函数、中序遍历函数、后序遍历函数。(2)建树函数定义一个输入的数是字符型的,当ch为空时,T就为空值,否则的话就分配空间给T,T就指向它的结点,然后左指针域指向左孩子,右指针指向右孩子,若还有,继续调用,依次循环下去,直到ch遇到空时,结束。最后要返回建立的二叉树T。(3)先序遍历函数根据先序遍历规则,当T为非空时,先输出结点处的数据,指针指向左、右孩子,依次进行下去。(4)中序遍历函数根据中序遍历规则,当T为非空时,先左指针指向左孩子数据,然后输出结点处的数据,再右指针指向右孩子,依次进行下去。(5)后序遍历函数根据后序遍历规则,当T为非空时,先右指针指向右孩子,然后左指针指向左孩子,最后输出结点处的数据,依次进行下去。:(1)跟递归遍历二叉树的前提一样,首先应该创建一个二叉树,同样使用先序递归的方式创建二叉树。 (2)然后是中序,先序,后序非递归遍历二叉树。 (3)中序非递归遍历二叉树的思想是:首先是根节点压栈,当根节点的左子树不是空的时候,左子树压栈。直到左子树为空的时候,不再压栈。将栈顶元素出栈,访问栈顶元素,并将栈顶的右子树进栈。当右子树的左子树不是空的时候,左子树一直进栈,直到左子树为空,则不再进栈。重复上面的操作,直到栈空的时候。 (4)先序非递归遍历二叉树的思想是:首先是根节点进栈,然后当栈不为空的时候,将栈顶元素出栈,然后访问。同时将出栈元素的右子树进栈,左子树进栈。重复上面的操作,直到栈为空。 (5)后序非递归遍历二叉树的思想:首先是根节点进栈,当根节点的左子树不为空的时候,左子树进栈,直到左为空的时候,左子树不再进栈。指针指向的是右子树,当右子树为空的时候,直接访问根节点。当右子树不为空的时候,则右子树的指针进栈,当右子树的左子树不为空的时候,则左也进栈,直到左为空。重复上面的操作,直到栈为空的时候,则遍历树完成。二、、#include""#include""#include<>#include<stack>typedefstructnode{chardata;structnode*lchild,*rchild;}BinTnode;typedefBinTnode*BinTree;//定义二叉树类型的指针/*先序创建二叉树*/intCreateBinTree(BinTree*T){charch; *T=(BinTree)malloc(sizeof(BinTnode));if(!*T)printf("overflow");do{ ch=getchar(); if(ch=='') {*T=NULL; return0; } else{ (*T)->data=ch; CreateBinTree(&((*T)->lchild)); CreateBinTree(&((*T)->rchild)); return1; } }while(ch!='\0');}/*中序递归遍历*/voidInorderTransverse(BinTrees){ if(s) { InorderTransverse(s->lchild); printf("%c",s->data); InorderTransverse(s->rchild); }}//先序递归遍历二叉树voidPreOrderTranverseTree(BinTrees){ if(s) { printf("%c",s->data); PreOrderTranverseTree(s->lchild); PreOrderTranverseTree(s->rchild); }}//后序递归遍历二叉树voidPostOrderTranverseTree(BinTrees){ if(s) { PreOrderTranverseTree(s->lchild); PreOrderTranverseTree(s->rchild); printf("%c",s->data); }

最近更新

长沙德克士(万家丽广场店)采购环节内部控制.. 12页

空气分级对降低煤粉工业锅炉氮氧化物排放的实.. 3页

税收筹划在不动产转让中的应用 3页

神南矿区5-2煤运输机断链原因分析及预防 3页

磷酸根和镉离子在羟基铁改性膨润土表面的协同.. 3页

碳纤维上浆技术对其可织性能的影响 3页

硝酸装置仪表故障在线处理的探讨 4页

砂性土中土拱演变阶段及影响因素试验探究 3页

矿井水位监测与控制系统的设计研究 3页

石油化工工程建设脚手架安全管理问题分析 3页

英语补缺作文和词汇 31页

历年高考优秀作文:反馈有准度,处事亦从容 2页

艺术空间项目展览方案策划书 16页

腔镜辅助阴式子宫切除术的手术配合 20页

胃癌分型与治疗原则 33页

2025年龟兔赛跑寓言作文400字 5页

2025年龙年网络科技四个字公司最吉利好名300个.. 5页

2025年龙年网络科技三个字公司名字参考 5页

2025年龙年易经吉利的女孩名字 12页

2025年龙年好听稀少的焦姓女孩名字 5页

2025年龙年信息技术两个字公司好名全集00个 11页

2025年黑龙江省专升本考试时间2025 5页

肱骨外科颈骨折护理常规 16页

2025年高考鼓励暖心句子 10页

2025年高考语文复习计划 15页

2025年高考英语备考策略是什么 5页

2025年高考理想满分作文 8页

苏卫单招校测2025试卷 9页

《黄河颂》33694省公开课一等奖全国示范课微课.. 29页

部编版九年级语文上册必背古诗文 8页