二叉树的非递归遍历

二叉树的非递归遍历

大家好,又见面了,我是全栈君。

先写下这个问题的模式

def preorderTraversal(self, root):
	if root == None: return []
	re = []
	insert root to stack s
	while s not empty:
		cur_root = top of stack s
		s.pop()
		how to handle cur_root
		how to handle cur_root.left
		how to handle cur_root.right

首先我们要把非空的root节点入栈,在循环里不断的推断出栈,然后处理栈顶元素及左孩子结点和右孩子结点。

我们先看下当前的栈顶元素怎么处理。先根遍历的顺序是:【根 左 右】。而我们每次处理的栈顶元素的身份事实上都恰好是根。所以我们就能够直接把这个根几点输出或放入结果容器中;那么其左孩子和右孩子怎样处理呢?既然是模拟递归,那么肯定要入栈进行保存的,谁先入栈呢?考虑到栈的性质,我们应该让其右孩子先入栈,左孩子后入栈,这样,栈顶就是左孩子,下次先出栈的就是左孩子。这样就符合先根遍历的顺序了。

再回过头来看下在左右孩子没入栈之前。我们不过获得了栈顶元素。该元素还依旧在栈中,那么它在栈中还有意义吗?非常明显没有意义了,由于它的信息我们已经输出,而其左右孩子在入栈后就再也不须要它了,所以就应该在左右孩子入栈前将其pop掉。

	def preorderIter(self, root):
		if None == root: return []
		re = []; s = []
		s.append(root)

		while len(s):
			cur_root = s.pop()
			print cur_root.val
			re.append(cur_root.val)

			if cur_root.right:
				s.append(cur_root.right)
			if cur_root.left:
				s.append(cur_root.left)
		return re

相同。后根遍历也是如此。尽管后根的遍历是【左 右 根】,可是我们毕竟是知道根要放在哪里。差别就是子节点的入栈顺序的变化。

	def postorderIter(self, root):
		if None == root:
			return
		re = [] # store results
		s = [] # node stack
		s.append(root)
		while len(s):
			cur_root = s.pop()
			re.insert(0,cur_root.val)
			if cur_root.left:
				s.append(cur_root.left)
			if cur_root.right:
				s.append(cur_root.right)
		return re

麻烦点的应该是中根遍历【左 根 右】。如前所述,我们处理的当前栈顶节点是视为根结点的,可是这个根结点却不知该放在结果中的哪里,放在前面,前面应该是左的位置。放在右面,右边应该是右孩子的位置,放中间?哪里算中间?1-10, 2 是中间还是3是中间?我们不确定。由于左右孩子的个数我们无从得知。

看来此时的栈顶元素不能像先根和后根那样。直接输出,还得在栈里面挤一下才好,不然总不能直接丢弃。

之所以当前的栈顶根不能输出,是由于它的左还没有确定,那么我们仅仅要把它的左都输出了。就能够确定当前根的位置了。

def inorderIter(self, root):
		if None == root: return []
		re = []
		s = []
		s.append(root)
		while len(s):
			cur_root = s[-1]
			# push, until the last letf
			while cur_root.left:
				s.append(cur_root.left)
				cur_root = cur_root.left
			# pop, until one node has right
			while len(s):
				cur_root = s[-1]
				print cur_root.val
				re.append(cur_root.val)
				s.pop()
				if cur_root.right:
					s.append(cur_root.right)
					break
		return re

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115871.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • fpga编程语言VHDL_vhdl和fpga

    fpga编程语言VHDL_vhdl和fpga硬件新手疑问1:大家都在争硬件开发是选择单片机,DSP,ARM还是FPGA呢?以我个人经验,我也是在硬件方面做了几年的老油条了,大学时玩过单片机,也就是大家常说的C51,C52,单片机驱动个流水灯还行,但是研究生阶段遇到的很多问题,单片机就有心无力了。至于ARM,DSPorFPGA,由于研一做无人机做了DSP的项目,鄙人觉得DSP入手比较难,但是DSP主攻方向是算法研究的,用于算法处理,绝对是…

  • linux如何退出编辑状态_linux编辑文件命令 vi

    linux如何退出编辑状态_linux编辑文件命令 vilinux退出编辑模式的命令linux退出编辑模式的命令有:vim有三种模式,注意:这三种模式有很多不同的叫法,我这里是按照鸟哥的linux书中的叫法。一般指令模式、编辑模式、指令列命令模式1.vim文件名进入一般模式;2.按i进行编辑进入编辑模式;(或者I,o,O,a,A,r,R)3.编辑结束,按ESC键跳到一般模式模式;4.按:进入指令列命…

  • idea2019最新可用激活码_通用破解码

    idea2019最新可用激活码_通用破解码,https://javaforall.cn/100143.html。详细ieda激活码不妨到全栈程序员必看教程网一起来了解一下吧!

  • Java集合篇:HashMap原理详解(JDK1.8)

    Java集合篇:HashMap原理详解(JDK1.8)

  • 安防监控基础知识

    安防监控基础知识针对安防视频监控方面的基础知识UDP:用户数据报协议(无连接,封装实时性强的网络音频数据)TCP:传输控制协议(面向连接,传输实时性强的音频流)HTTP:超文本传输协议,网络摄像机通过HTTP提供web访问功能,将音频数据经过复杂网络传输.RTP:实时传输协议,提供时间信息流和实现流同步(本身不提供可靠的传输机制和流量控制)RTCP:实时传输控制协议,提供可靠的…

  • 笔记本外接显示器怎么投屏(笔记本电脑怎么连接显示屏)

    “开始”右键,点击搜索->在搜索框中输入“投影”->“投影到第二屏幕”,点击打开可以看到四种模式:仅电脑屏幕;仅第二屏幕;复制;扩展选择“扩展”桌面空白处右键->显示设置->显示点击标识,确认屏幕1(一般是笔记本原屏幕),屏幕2(一般是外接显示屏)分别是哪块屏幕。根据自己的需要设置主显示器然后就可以愉快的双屏工作啦~…

发表回复

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

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