数据结构中二叉树的生成及遍历非递归算法浅析

《数据结构中二叉树的生成及遍历非递归算法浅析》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、万方数据Vocabulary≤总第172期数据结构中二叉树的生成及遍历非递归算法浅析吉冬梅(吉林农业工程职业技术学院四平136100)摘要本文主要介绍数据结构中二叉树的生成，以及二叉树的先序、中序和后序的非递归算法。关键词二叉树二叉树先序遍历二叉树中序遍历二叉树后序遍历中图分类号TP311．12文献标识码A文章编号100104—5265ABriefAnalysisontheGenerationofaBinaryTreeandTraversalNon-recursiveAlgorithminDataStructurejiDongmei

2、(JihnAgriculturalEngineeringVocationalTechnologyCoUegeSiping136000)AbstactThispaperdescribesthegenerationofbinarytreedatastructure，a8wellasthebinarytreepreorder，inorderandpost-ordernon-recursivealgorithm．KeywordsBinarytreePreorderbinarytreetraversalBinarytreeinordertra

3、versalPost-orderbinarytreetraversal一、引言#include“malloc．h”--X树是一种蕈要的树形结构，其结构规整。许多实际问#defineNULL0题抽象出来的数据结构往往是二叉树的形式，而且其存储结构typedetstructbtnodei及运算都较为简练，因此，二叉树在数据结构课程中显得特别chardata；重要，这里我们先了解一下二叉树。structbtnodelchild，rehild；二叉树是由结点的有限集合构成，这个有限集合或者为空}Btree；集，或者是由一个根节点及两棵互不相

4、交的分别称之为这个根Btree+Q[maxsize]；的左子树和右子树的二叉树组成。从定义来看，二叉树定义是一Btree+creatreeOi个递归定义，但由于学生对递归算法的理解存在一些误区，同时cbarch；递归算法效率较低，并且在实际应用中有些问题也不允许调用-nttrent，rear；递归算法，故有关二叉树的试题通常要求采用非递归算法，这就Btree8t，+s；使得掌握二叉树的生成及遍历的非递归算法成为必要。t=NuLL；二、二叉树的生成1砌科；建立一个--y．．树是指在内存中建立ZJ．树的存储结构，这1：“～’．，、里讨论

5、建立一个二叉链表的方式生成一个二叉树。要建立一个c?2呼：l，凡、二叉链表，需按照完全二叉树的层次顺序，依次输入结点信息建whl‘。【oh!d#。，立二叉链表。对于一般的二叉树，必须添加一些虚结点，使其成I．s，=Nu兰望耋葺凑嚣鬈鬻麓纛嚣翕凳黧意星譬翟装：，nmn讯赫“酬，；设置一个队列，队列是一个指针类型的数组，保存已输入的结点’-、⋯。”⋯”⋯一一⋯“’的地址。根据对为指针奇偶数的判断，来决定把字符放到左孩子8’>da诅=cn；结点中还是右孩子结点中，这样就能生成想要的二叉树。8一>l。hild=NULL；#deftnem嘲i

6、ze1008～>他}Iild2NULL；#include“stdio．h，，脚r++；Q【re盯】-8；‘30‘办公自动化杂志圜U盟—一丽r—]墨网万方数据if(rear==1)T=s：else{if(s&&Q[front])if(rear％2==0)Q[front]->lchild=s；elseQ[front]->rchild=s；if(rear％2==1)f南nt++；lch=getchar()；lreturnT；}三、二叉树的先序、中序、后序遍历上面虽然已经生成二叉树，但实际上用户生成的二叉树是抽象，用户并不太确信已经生成的二

7、叉树是否是自己想要的，于是，可以编制输出程序进一步验证这个已经存在的二叉树的正确性。二叉树的遍历就是对二叉树的每一个结点访问一次且仅访问一次。我们通过二叉树的序遍历的非递归算法来验证其正确性。二叉树非递归遍历是用显示栈来存储二叉树的结点指针。1、先序遍历使用一个栈，首先将根结点入栈，开始循环；从战中退出当前结点，先访问它，然后将其右结点人栈，再将其左结点入栈，如此直到栈空为止。Voidporder(Btree+面{Btree8stack[maxsize],*p；inttop=一l：if(T!=NULL){top++；stack[to

8、p]=T；while(top>-1){p=stack[top]；Top一；prinft(“％c",p->data)；if(p->right!=NUEL){top++；staek[top]=p->right；}if(p->lefl!=N