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

二叉树后序遍历的非递归实现_二叉树的后序遍历非递归详细一、递归实现前序,序,后序遍历;对于二叉树,前面已经采用递归的方式实现的其前序,中序,后序遍历,具体请参见: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)


相关推荐

  • 改名了,一个新的开始

    怕什么真理无穷进一步有近一步的欢喜这个是我电脑桌面壁纸1又有一段时间没来这里了,看了上次发文的日期是2021年10月31日,已经快过去三个月了。上次发文还是2021现在已经到2022年了,…

  • python关于缩进_python缩进符号

    python关于缩进_python缩进符号在写作文的时候,老师会告诉我们每段要空两格,这两个空格标志着一个新的段落开始了。在编写程序的时候,我们也要采用类似的方式,通过缩进来表示代码块的开始和结束。认识缩进在之前学过的的例子中,我们所编写的都是简单的表达式语句,没有缩进。但是,要创建复合语句,就需要用到缩进这个重要的概念。我们可以把许多代码行组织到一个代码块中,其中的每一行代码的开始,都保持相同的空格数,通过查看代码行前面的空格数,就可以…

    2022年10月13日
  • webpack devtools_webpack loader和plugin的区别

    webpack devtools_webpack loader和plugin的区别前言devtool也是之前常用的一个配置,我们稍微了解下吧,不研究太深,毕竟现在都不怎配置他。内容devtool是配置sourceMap的。sourceMap大家都知道,我们本地或者测试环境出了错误,可以在source中迅速定位错误,用到的就是.map(map文件),这个文件中是源文件映射(主要是源文件代码)。但是我们在network中看不到.map文件的请求,盲猜一波是浏览器做了屏蔽,不让我们看这种请求。(毕竟是源码,我单独下载map文件是可以下载下来的)接下来,当devtool被配置为

  • vi的撤销命令

    vi的撤销命令

    2021年10月22日
  • C语言中u8 u16 u32含义,有关stm32的问题,程序里面的u8、u16这些是什么意思啊「建议收藏」

    C语言中u8 u16 u32含义,有关stm32的问题,程序里面的u8、u16这些是什么意思啊「建议收藏」u8是unsignedchar,u16是unsignedshort,u32是unsignedlong。u8,u16,u32都是C语言数据类型,分别代表8位,16位,32位长度的数据类型,一个字节是8位,所以u8是1个字节,u16是2个字节,u32是4个字节。可以在stm32库头文件中找到数据类型的声明在stdint.h中:typedefunsignedcharuint8_t;typed…

  • oracle 触发器通知,Oracle触发器详细介绍

    oracle 触发器通知,Oracle触发器详细介绍欢迎进入Oracle社区论坛,与200万技术人员互动交流>>进入触发器是特定事件出现的时候,自动执行的代码块。类似于存储过程,但是用户不能直接调用他们。功能:1、允许/限制对表的修改2、自动生成派生列,比如自增字段3、强制数据一致性4、提供欢迎进入Oracle社区论坛,与200万技术人员互动交流>>进入触发器是特定事件出现的时候,自动执行的代…

发表回复

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

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