二叉树后序遍历的非递归实现_二叉树的后序遍历非递归详细

二叉树后序遍历的非递归实现_二叉树的后序遍历非递归详细一、递归实现前序,序,后序遍历;对于二叉树,前面已经采用递归的方式实现的其前序,中序,后序遍历,具体请参见:http://blog.csdn.net/dai_wen/article/details/78955411那么,如何采用非递归的方式遍历树呢?下面,以实现中序遍历二叉树为主题展开:二、非递归实现中序遍历:1,结构:首先,对于中序遍历,我们知道,原则是先走到的结点后访问,后走到的结点

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新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账号...

(0)
blank

相关推荐

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号