大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
一、递归实现前序,序,后序遍历;
对于二叉树,前面已经采用递归的方式实现的其前序,中序,后序遍历,具体请参见:
http://blog.csdn.net/dai_wen/article/details/78955411
那么,如何采用非递归的方式遍历树呢?
下面,以实现中序遍历二叉树为主题展开:
二、非递归实现 中序遍历:
1,结构:
首先,对于中序遍历,我们知道,原则是先走到的结点后访问,后走到的结点先访问,这显然是栈的结构;
2,访问结点的具体步骤:
结点的所有路径情况:
step1: 如果当前结点有左子树,则该结点入栈;
———–如果没有左子树,则访问该结点;
step2:如果结点有右子树,则重复step1;
——— 如果没有右子树,则回退,让此时的栈顶元素出栈,访问栈顶元素,并访问栈顶元素的右子树,重复step1,2
strp3:如果栈为空,则表示遍历结束;
注意:入栈结点本身没有被访问过,同时,其右子树也没有被访问过;
3,流程图:
那么,根据文字,画出如下流程图:
//下面,举个例子:
如下所示的五个结点的二叉树,其非递归中序遍历如下图所示:
(1)实现思路图如下所示:
(2)具体程序实现:
#include <iostream>
#include <stack>
using namespace std;
//二叉链表
typedef struct BiTNode
{
int data;
struct BiTNode *lchild, *rchild; //左孩子 右孩子
}BiTNode,*BiTree;
/*树的形状
1
2 3
4 5
*/
BiTNode *GoFarLeft(BiTNode *T, stack<BiTNode *> &s)//一直向左走函数
{
if (T == NULL)
{
return NULL;
}
//如果T有左孩子 入栈
while (T->lchild)
{
s.push(T);
T= T->lchild;//一直往左走
}
return T; //找到一个没有左孩子的节点,就是中序遍历的起点
}
void InOrder2(BiTNode *T)
{
stack<BiTNode *>s;
BiTNode *t = GoFarLeft(T, s); //中序遍历的起点
while(t)
{
printf("%d ", t->data);
if (t->rchild) //如果有右孩子 重复12步骤
{
t = GoFarLeft(T->rchild, s);
}
else if (!s.empty()) //如果没有右孩子,说明该节点的树放完毕,需要返回。
{
t = s.top(); //非空就从栈顶拿元素
s.pop();
}
else //如果没有右孩子,并且栈为空 t = NULL;
{
t = NULL;
}
}
}
int main()
{
BiTNode b1, b2, b3, b4, b5;
BiTNode *pNewTree = NULL;
memset(&b1, 0, sizeof(BiTNode));
memset(&b2, 0, sizeof(BiTNode));
memset(&b3, 0, sizeof(BiTNode));
memset(&b4, 0, sizeof(BiTNode));
memset(&b5, 0, sizeof(BiTNode));
b1.data = 1;
b2.data = 2;
b3.data = 3;
b4.data = 4;
b5.data = 5;
//构建树关系
b1.lchild = &b2;
b1.rchild = &b3;
b2.lchild = &b4;
b3.lchild = &b5;
InOrder2(&b1);
return 0;
}
(3)程序实现结果:
(4)总结,非递归实现中序遍历,其关键在于判断其左右子树存不存在,处理好压栈和出栈的顺序即可,只要仔细一些,就没什么问题了
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/193880.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...