二叉树遍历C语言(递归,非递归)六种算法

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

二叉树的遍历-1-数据结构(双语)——项目文档报告用两种方式实现表达式自动计算专业:班级:指导教师:姓名:学号:二叉树的遍历-2-目录一、设计思想……………………………………………………….01二、算法流程图…………………………………………………….02三、源代码………………………………………………………….04四、运行结果……………………………………………………….11五、遇到的问题及解决…………………………………………….11六、心得体会……………………………………………………….12二叉树的遍历-3-一、设计思想二叉树的遍历分为三种方式,分别是先序遍历,中序遍历和后序遍历。先序遍历实现的顺序是:根左右,中序遍历实现的是:左根右,后续遍历实现的是:左右根。根据不同的算法分,又分为递归遍历和非递归遍历。递归算法:1.先序遍历:先序遍历就是首先判断根结点是否为空,为空则停止遍历,不为空则将左子作为新的根结点重新进行上述判断,左子遍历结束后,再将右子作为根结点判断,直至结束。到达每一个结点时,打印该结点数据,即得先序遍历结果。2.中序遍历:中序遍历是首先判断该结点是否为空,为空则结束,不为空则将左子作为根结点再进行判断,打印左子,然后打印二叉树的根结点,最后再将右子作为参数进行判断,打印右子,直至结束。3.后续遍历:指针到达一个结点时,判断该结点是否为空,为空则停止遍历,不为空则将左子作为新的结点参数进行判断,打印左子。左子判断完成后,将右子作为结点参数传入判断,打印右子。左右子判断完成后打印根结点。非递归算法:1.先序遍历:首先建立一个栈,当指针到达根结点时,打印根结点,判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈,将左子作为新的根结点进行判断,方法同上。若当前结点没有左子,则直接将右子打印,同时将右子作为新的根结点判断。若当前结点没有右子,则打印左子,同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子,则当前结点为叶子结点,此时将从栈中出栈一个元素,作为当前的根结点,打印结点元素,同时将当前结点同样按上述方法判断,依次进行。直至当前结点的左右子都为空,且栈为空时,遍历结束。2.中序遍历:首先建立一个栈,定义一个常量flag(flag为0或者1),用flag记录结点的左子是否去过,没有去过为0,去过为1,默认为0.首先将指针指向根结点,将根结点入栈,然后将指针指向左子,左子作为新的结点,将新结点入栈,然后再将指针指向当前结点的左子,直至左子为空,则指针返回,flag置1,出栈一个元素,作为当前结点,打印该结点,然后判断flag,flag为1则将指针指向当前结点右子,将右子作为新的结点,结点入栈,再次进行上面的判断,直至当前结点右子也为空,则再出栈一个元素作为当前结点,一直到结束,使得当前结点右子为空,且栈空,遍历结束。3.后续遍历:首先建立两个栈,然后定义两个常量。第一个为status,取值为0,1,2.0代表左右子都没有去过,1代表去过左子,2,代表左右子都去过,默认为0。第二个常量为flag,取值为0或者1,0代表进左栈,1代表进右栈。初始时指针指向根结点,判断根结点是否有左子,有左子则,将根结点入左栈,status置0,flag置0,若没有左子则判断结点有没有右子,有右子就把结点入右栈,status置0,flag置1,若左右子都没有,则打印该结点,并将指针指向空,此时判断flag,若flag为0,则从左栈出栈一个元素作为当前结点,重新判断;若flag为1则从右栈出栈一个元素作为当前结点,重新判断左右子是否去过,若status为1,则判断该结点有没有右子,若有右子,则将该结点入右栈,status置1,flag置1,若没有右子,则打印当前结点,并将指针置空,然后再次判断flag。若当前结点status为2,且栈为空,则遍历结束。若指针指向了左子,则将左子作为当前结点,判断其左右子情况,按上述方法处理,直至遍历结束。二叉树的遍历-4-二、算法流程图图1二叉树的建立用先序方法建立二叉树,为每个结点定义左右子,用0代表空,得到上述二叉树图2非递归二叉树遍历先序首先建立一个栈,当指针到达根结点时,打印根结点,判断根结点是否有左子和右子。有左子和右子的话就打印左子同时将右子入栈,将左子作为新的根结点进行判断,方法同上。若当前结点没有左子,则直接将右子打印,同时将右子作为新的根结点判断。若当前结点没有右子,则打印左子,同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子,则当前结点为叶子结点,此时将从栈中出栈一个元素,作为当前的根结点,打印结点元素,同时将当前结点同样按上述方法判断,依次进行。直至当前结点的左右子都为空,且栈为空时,遍历结束。二叉树的遍历-5-图3非递归二叉树遍历中序中序遍历:首先建立一个栈,定义一个常量flag(flag为0或者1),用flag记录结点的左子是否去过,没有去过为0,去过为1,默认为0.首先将指针指向根结点,将根结点入栈,然后将指针指向左子,左子作为新的结点,将新结点入栈,然后再将指针指向当前结点的左子,直至左子为空,则指针返回,flag置1,出栈一个元素,作为当前结点,打印该结点,然后判断flag,flag为1则将指针指向当前结点右子,将右子作为新的结点,结点入栈,再次进行上面的判断,直至当前结点右子也为空,则再出栈一个元素作为当前结点,一直到结束,使得当前结点右子为空,且栈空,遍历结束。二叉树的遍历-6-图4非递归二叉树遍历后序首先建立两个栈,然后定义两个常量。第一个为status,取值为0,1,2.0代表左右子都没有去过,1代表去过左子,2,代表左右子都去过,默认为0。第二个常量为flag,取值为0或者1,0代表进左栈,1代表进右栈。初始时指针指向根结点,判断根结点是否有左子,有左子则,将根结点入左栈,status置0,flag置0,若没有左子则判断结点有没有右子,有右子就把结点入右栈,status置0,flag置1,若左右子都没有,则打印该结点,并将指针指向空,此时判断flag,若flag为0,则从左栈出栈一个元素作为当前结点,重新判断;若flag为1则从右栈出栈一个元素作为当前结点,重新判断左右子是否去过,若status为1,则判断该结点有没有右子,若有右子,则将该结点入右栈,status置1,flag置1,若没有右子,则打印当前结点,并将指针置空,然后再次判断flag。若当前结点status为2,且栈为空,则遍历结束。若指针指向了左子,则将左子作为当前结点,判断其左右子情况,按上述方法处理,直至遍历结束。三、源代码下面给出的是用递归算法实现的程序的源代码:#includestdio.h#includestdlib.h//用递归的方式遍历二叉树typedefstructnode//定义二叉树的结点{intdata;//结点的数据structnode*lChild,*rChild;//结点左右子}Node;inti=-1;//控制下面函数中循环的Node*buildTree(int*b)//产生二叉树(利用先序递归产生){Node*p;//创建一个根结点指针if(b[++i]==0)p=NULL;//如果传入的当前值为0则设其为空结点else{p=(Node*)malloc(sizeof(Node));//开辟内存p-data=b[i];//设置当前结点的数据p-lChild=buildTree(b);//左子结点p-rChild=buildTree(b);//右子}returnp;//把创建的树的根节点返回}voidpreOrder(Node*root)//前序遍历{二叉树的遍历-7-if(root!=0)//如果根节点不为0{printf(%d,root-data);//打印当前结点preOrder(root-lChild);//指向左子preOrder(root-rChild);//指向右子}}voidinOrder(Node*root)//中序遍历{if(root!=0)//如果根节点不为0{inOrder(root-lChild);//指向左子printf(%d,root-data);//打印当前结点inOrder(root-rChild);//指向右子}}voidpostOrder(Node*root){if(root!=0){postOrder(root-lChild);//指向左子postOrder(root-rChild);//指向右子printf(%d,root-data);//打印当前结点}}voidmain(){//按先序次序输入树的结点(非0整数)来创建一个树空结点用0表示inta[]={1,2,4,0,7,0,0,0,3,5,0,0,6,8,0,0,9,0,0};int*b=a;//将指向数组首地址的指针传给bulidTree函数来创建树Node*root=buildTree(b);printf(用递归方法\n\n前序遍历:);//打印提示内容preOrder(root);//调用前序遍历函数printf(\n中序遍历:);//打印提示内容inOrder(root);//调用中序遍历函数printf(\n后序遍历:);//打印提示内容postOrder(root);//调用后序遍历函数getch();}二叉树的遍历-8-下面给出的是用非递归算法实现的程序的源代码:#includestdio.h#includestdlib.h//用非递归的方式遍历二叉树typedefstructnode//定义二叉树的结点{intdata;//结点的数据structnode*lChild,*rChild;//结点左右子}Node;typedefstruct//创建栈{Node*bottom;//栈底指针Node*top;//栈顶指针}Stack;voidinit(Stack*s)//初始化栈{s-bottom=(Node*)malloc(100*sizeof(Node));//为指针开辟内存s-top=s-bottom;//栈顶指针指向栈底指针}intisEmpty(Stacks)//判断栈是否为空的函数{if(s.top==s.bottom)return1;//栈空返回1elsereturn0;//不为空返回0}voidpush(Stack*s,Nodenode)//栈的push方法{*(s-top++)=node;//给栈顶赋值然后top+1}Nodepop(Stack*s)//出栈函数{Nodenode;//声明一Node类型遍量node=*(--(s-top));//node为栈顶元素然后top-1returnnode;//返回pop出的结点}Nodepeek(Stack*s)//看栈顶元素{return*(s-top-1);//返回栈顶元素}typedefstruct//创建栈(MyStack)结构体{Node*bottom;//栈底指针Node*top;//栈顶指针}MyStack;二叉树的遍历-9-voidinit1(MyStack*s)//初始化栈{s-bottom=(Node*)malloc(100*sizeof(Node));//开辟内存s-top=s-bottom;//栈顶指针指向栈底指针}voidpush1(MyStack*s,Nodenode)//进栈方法{*(s-top++)=node;//给栈顶赋值然后top+1}Nodepop1(MyStack*s)//出栈函数{Nodenode;//声明一Node类型遍量node=*(--(s-top));//node为栈顶元素然后top-1returnnode;//返回pop出的结点}Nodepeek1(MyStack*s)//查栈顶元素{return*(s-top-1);//返回栈顶元素}intisEmpty1(MyStacks)//判断栈是否为空{if(s.top==s.bottom)retu

1 / 14
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功