文档介绍：该【用递归非递归两种方法遍历二叉树】是由【泰山小桥流水】上传分享，文档一共【13】页，该文档可以免费在线阅读，需要了解更多关于【用递归非递归两种方法遍历二叉树】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。用递归、非递归两种方法遍历二叉树
一、设计思想
二叉树的遍历分为三种方式,分别是先序遍历,中序遍历和后序遍历。先序遍历实现的序次是:根左右,中序遍历实现的是:左根右,后续遍历实现的是:左右根。
依据不一样的算法分,又分为递归遍历和非递归遍历。
递归算法:
:
先序遍历就是第一判断根结点能否为空,为空则停止遍历,不为空则将左子作为新的根
结点重新进行上述判断,左子遍历结束后,再将右子作为根结点判断,直至结束。到达每一
个结点时,打印该结点数据,即得先序遍历结果。
:
中序遍历是第一判断该结点能否为空,为空则结束,不为空则将左子作为根结点再进行判断,打印左子,而后打印二叉树的根结点,最后再将右子作为参数进行判断,打印右子,
直至结束。
:
指针到达一个结点时,判断该结点能否为空,为空则停止遍历,不为空则将左子作为新的结点参数进行判断,打印左子。左子判断完成后,将右子作为结点参数传入判断,打印右
子。左右子判断完成后打印根结点。
非递归算法:
:
第一成立一个栈,当指针到达根结点时,打印根结点,判断根结点能否有左子和右子。
有左子和右子的话就打印左子同时将右子入栈,将左子作为新的根结点进行判断,方法同上。若当前结点没有左子,则直接将右子打印,同时将右子作为新的根结点判断。若当前结点没有右子,则打印左子,同时将左子作为新的根结点判断。若当前结点既没有左子也没有右子,则当前结点为叶子结点,此时将从栈中出栈一个元素,作为当前的根结点,打印结点元素,
同时将当前结点相同按上述方法判断,挨次进行。直至当前结点的左右子都为空,且栈为空时,遍历结束。
:
第一成立一个栈,第一将指针指向根结点,将根结点入栈,而后将指针指向左子,左子
作为新的结点,将新结点入栈,而后再将指针指向当前结点的左子,直至左子为空,则指针
返回,出栈一个元素,作为当前结点,打印该结点,而后将指针指向当前结点右子,将右子
作为新的结点,结点入栈,再次进行上边的判断,直至当前结点右子也为空,则再出栈一个
元素作为当前结点,向来到结束,使得当前结点右子为空,且栈空,遍历结束。
:
第一从根节点开始遍历,看根节点能否为空,假如根节点不为空,将根节点的元素压入
栈中,连续遍历,假如根节点有左子,索引挪动到左子,并以左子为根节点连续遍历。假如左子不为空,则索引挪动到左子并入栈;假如左子为空,索引挪动到栈顶元素所在的节点,
假如此节点的右子不为空而且右子没有被接见过,则索引挪动到右子,不然接见栈顶元素并
输出,而且定义此节点为被接见过得节点,栈顶元素出栈,树节点定义为NULL,连续遍历。
二、算法流程图
递归算法:
-1-
用递归、非递归两种方法遍历二叉树
创办二叉树
调用自己
调用对应函数
输出结果
图1递归算法流程图
先序非递归遍历:
获取根节点
输出当前节点
判断当前节点
能否存在左子
不存在
当前节点
能否存在右子
不存在
出栈,当前节
不为空栈能否为空
点为出栈元
素
图2先序遍历的非递归算法流程图

存在当前节点的元素入栈,当前节点挪动到左子上
存在
当前节点跳
到右子上
为空结束
-2-
用递归、非递归两种方法遍历二叉树
中序非递归遍历:
获取根节点
判断当前节点
能否存在左子
不存在
输出当前节点
判断当前节点
能否存在右子
不存在
出栈,当前节
不为空
点为出栈元栈能否为空
素

存在当前节点的元素
入栈,当前节点
挪动到左子上
当前节点跳
存在
到右子上
为空
结束
图3中序遍历的非递归算法流程图
-3-
用递归、非递归两种方法遍历二叉树
后序非递归遍历:
获取根节点
判断当前节点
能否存在左子
不存在
判断当前节点
能否存在右子
不存在
输出当前节点
出栈,当前节
不为空
点为出栈元栈能否为空
素

当前节点的元素
存在
入栈,当前节点
挪动到左子上
存在当前节点跳
到右子上
为空
结束
图4后序遍历的非递归算法流程图
-4-
用递归、非递归两种方法遍历二叉树
三、源代码
前序非递归
#include<>
structelement//用结构体成立二叉树元素
{
structelement*lchild;
intdata;
structelement*rchild;
};
intmain( )
{
inti=1;
structelement*stack[30];
structelementa,b,c,d,e;//成立二叉树
=1;=2;=3;=4;=5;
=&b;=&c;
=&d;=&e;=0;=0;
=0;=0;=0;=0;
stack[i]=&a;
while(i!=0)//用数组逐一办理二叉树的元素
{
while(stack[i]!=0)//取左子树直至为空
{
printf("%d\n",(*(stack[i])).data);//接见元素的数据部分
i++;
stack[i]=(*(stack[i-1])).lchild;
}
i--;//去掉空元素
if(i!=0)
{
stack[i]=(*(stack[i])).rchild;//取右子树
}
}
getch( );
}
中序非递归
#include<>
structelement//用结构体成立二叉树元素
-5-
//用数组逐一办理二叉树的元素
用递归、非递归两种方法遍历二叉树
{
structelement*lchild;
intdata;
structelement*rchild;
};
intmain( )
{
inti=1;
structelement*stack[30];
structelementa,b,c,d,e;//成立二叉树
=1;=2;=3;=4;=5;
=&b;=&c;
=&d;=&e;=0;=0;
=0;=0;=0;=0;
stack[i]=&a;
while(i!=0)
{
while(stack[i]!=0)
{
i++;
stack[i]=(*(stack[i-1])).lchild;
}//取左子树直至为空
i--;//去掉空元素
if(i!=0)
{
printf("%d\n",(*(stack[i])).data);//接见元素的数据部分
stack[i]=(*(stack[i])).rchild;//取右子树
}
}
getch( );
}
后序非递归
#include<>
structelement//用结构体成立二叉树元素
{
structelement*lchild;
intdata;
structelement*rchild;
};
intmain( )
{
-6-
用递归、非递归两种方法遍历二叉树
inti=-1,j=-1;
inttag[20];
structelement*p;
structelementstack[30];
structelementa,b,c,d,e;//成立二叉树
=1;=2;=3;=4;=5;
=&b;=&c;
=&d;=&e;=0;=0;
=0;=0;=0;=0;
p=&a;
while(p!=0||j!=-1)//元素非空或没有遍历完整部节点就不结束
{
while(p)//当p指向的节点存在时,将其压入栈中,把0压入标记栈中
{//并将p指向其左子树
stack[++i]=*p;
tag[++j]=0;
p=(*p).lchild;
}
if(j>-1)
{
if(tag[j]==1)//当有右子树接见标记时,接见当前节点的数据
{
printf("%d\n",stack[i].data);
i--;
j--;
}
else//没有右子树接见标记时,获得当前节点的的右子树
{//并将右子树接见标记置1
p=stack[i].rchild;
tag[j]=1;
}
}
}
getch( );
}
前序递归
#include<>
structelement//用结构体成立二叉树的元素
{
structelement*lchild;
intdata;
structelement*rchild;
-7-
用递归、非递归两种方法遍历二叉树
};
intmain( )
{
structelementa,b,c,d,e;
intpreRev(structelemente);//申明办理二叉树元素的递归方函数
//成立二叉树
=1;=2;=3;=4;=5;
=&b;=&c;
=&d;=&e;=0;=0;
=0;=0;=0;=0;
preRev(a);//调用递归函数对二叉树元素进行逐一办理
getch( );
}
intpreRev(structelemente)//定义递归函数
{
printf("%d\n",);
if()preRev(*);
if()preRev(*);
}
中序递归
#include<>
structelement//用结构体成立二叉树的元素
{
structelement*lchild;
intdata;
structelement*rchild;
};
intmain( )
{
structelementa,b,c,d,e;
intpreRev(structelemente);//申明办理二叉树元素的递归方函数
//成立二叉树
=1;=2;=3;=4;=5;
=&b;=&c;
=&d;=&e;=0;=0;
=0;=0;=0;=0;
preRev(a);//调用递归函数对二叉树元素进行逐一办理
getch( );
}
-8-
用递归、非递归两种方法遍历二叉树
intpreRev(structelemente)//定义递归函数
{
if()preRev(*);
printf("%d\n",);
if()preRev(*);
}
后序递归
#include<>
structelement//用结构体成立二叉树的元素
{
structelement*lchild;
intdata;
structelement*rchild;
};
intmain( )
{
structelementa,b,c,d,e;
intpreRev(structelemente);//申明办理二叉树元素的递归方函数
//成立二叉树
=1;=2;=3;=4;=5;
=&b;=&c;
=&d;=&e;=0;=0;
=0;=0;=0;=0;
preRev(a);//调用递归函数对二叉树元素进行逐一办理
getch( );
}
intpreRev(structelemente)//定义递归函数
{
if()preRev(*);
if()preRev(*);
printf("%d\n",);
}
四、运转结果
-9-
用递归、非递归两种方法遍历二叉树
前序递归:
图5前序递归运转结果
中序递归:
图6中序递归运转结果
-10-