二叉树遍历的非递归实现

二叉树遍历的非递归实现,第1张

二叉树遍历的非递归实现

复习数据结构的过程中,觉得二叉树前中后序遍历的非递归实现还是不太好想的,所以结合老师给出的思想,整理了一下自己的思路,记在这里,留日后翻看

分析

    递归实际就是栈的先进后出的性质,所以用栈来实现非递归算法。

    递归回溯的时候会重新获得当前状态的全部信息,但是非递归实现不会自然有这些,难点就是保存需要的信息。

先序遍历

对于任意节点,只要访问之后先后入栈其非空的右、左孩子即可

中序遍历

访问一个节点之前,其左子树的节点已经全部被访问过。

因此根据栈先进后出的特性,入栈一个节点之后,要入栈其左孩子,入栈左孩子后又得入栈左孩子的左孩子…就是说向左入栈到尽头。

这样在栈中访问栈顶时,他的左子树节点已经被全部d出(访问),这个栈顶就可以直接被访问。然后在根据上述规则入栈其右孩子…

后序遍历
			 p
		p.l		p.r
	  ..  ..   ..  ..

根据上边两个的思路,这个大概得按这个顺序入栈:p、p.r、p.l,d出顺序为p.l、p.r、p,后序序列。

不过由于后序遍历的特点,有一个问题:分支结点出现在栈顶时,既可能是正在构建栈的过程(比如接上,此时p.l为栈顶,该继续压栈),又可能是回溯的过程(比如d出了p.l和p.r后p成为栈顶,该访问了)。那究竟访问还是继续压栈呢?

因此我构建了第二个栈s2,用来同步保存s1中结点的深度。

对于任一状态下的栈顶p,满足如下条件之一时访问并d出p:

p无孩子,即p为叶结点

上一次输出结点的深度比p的大(正在回溯)

否则将p的子节点压入。

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/5703103.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-12-17
下一篇 2022-12-17

发表评论

登录后才能评论

评论列表(0条)

保存