最新消息:

PHP实现二叉树的后序非递归遍历算法(1)

PHP pengchengdewebxuexibiji 65浏览 0评论

什么是二叉树后序遍历

二叉树的后序遍历按照“左孩子-右孩子-根结点”的顺序进行访问。如下图:

PHP实现二叉树的后序非递归遍历算法(1)

遍历输出的结果为 DEBFCA

分析定义

1)一个节点有左孩子和右孩子的时候,不能早于它的左右孩子输出之前输出

2)一个节点同时没有左右孩子的时候,可以输出,但是如同DE的那种情况,D是上一级的左孩子,先输出,然后再输出E

3)一个节点有孩子,但是它的孩子都输出过了,那么这个节点输出。但是要遵循左子树优先

解题思路

我们利用栈先进后出的原理,让最早输出的左叶子节点D在栈的最上面,让右孩子在左孩子的下面,让后输出的根节点在栈的最下面。并且我们每次取栈顶元素作为下一个要访问的节点。思路明确后我们这样来实现

1)首先把root节点A压入堆栈,我们给这个堆栈起名stack,方便后面描述。

2)我们访问stack的栈顶元素,也就是A,判断A是否有子节点,这里有B和C,按照“右孩子在左孩子的下面”的思路,我们先把C压入stack,再把B压入stack

3)我们访问stack的栈顶元素,也就是B,判断B是否有子节点,这里有D和E,按照“右孩子在左孩子的下面”的思路,我们先把E压入stack,再把D压入stack

4)我们访问stack的栈顶元素,也就是D,判断D是否有子节点,无,我们输出它,出栈它。同时我们把它标记为pre_out,意思是上一次被输出的元素

5)我们访问stack的栈顶元素,也就是E,判断E是否有子节点,无,我们输出它,出栈它。同时我们把它标记为pre_out(覆盖了4里同名的标记,下面以此类推),表明E是上一次被输出的元素

6)我们访问stack的栈顶元素,也就是B,判断B是否有子节点,有。这次我们需要判断B的孩子是否都被输出过,我们判断它的左右孩子是否有一个和pre_out相等,如果有,则表明B的孩子都被输出。(思考:为什么?提示:一个节点和他的孩子是先后入栈的,顺序为节点、右孩子、左孩子)。这里确实B的孩子都输出了,那么B输出,同时出栈。同时我们把它标记为pre_out。

7)我们访问stack的栈顶元素,也就是C,判断C是否有子节点,这里有F,我们把F压入stack

8)我们访问stack的栈顶元素,也就是F,判断F是否有子节点,无,我们输出它,出栈它。同时我们把它标记为pre_out

9)我们访问stack的栈顶元素,也就是C,判断B是否有子节点,有。这次我们需要判断C的孩子是否都被输出过。判断访问同 6)。我们输出它,出栈它。同时我们把它标记为pre_out。

10)我们访问stack的栈顶元素,也就是A,判断A是否有子节点,有。这次我们需要判断A的孩子是否都被输出过。判断访问同 6)。我们输出它,出栈它。同时我们把它标记为pre_out。

11)我们访问stack的栈顶元素,为null,遍历结束。输出结果为 DEBFCA

练习

请根据以上的思路用php实现二叉树的后序非递归遍历算法。我会在下一个笔记中给出我写的一段程序。

转载请注明:PHP学习 » PHP实现二叉树的后序非递归遍历算法(1)

发表我的评论
取消评论

表情

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址