二叉树的后序遍历

马谦马谦马谦
马谦马谦马谦
马谦马谦马谦
611
文章
12
评论
2020年2月9日13:57:19 评论

一、后序遍历

后序遍历逻辑:优先访问左、右子节点,然后访问当前节点。

一个后序遍历的示例,它的后序遍历结果为[4, 2, 5, 6, 3, 1]:

二叉树的后序遍历

二、非递归实现

后序遍历的非递归实现比前序和中序的非递归实现要复杂很多,因为每个节点都可能有2个子节点,遍历的时候节点中并没有保存当前的状态,无法确定两个子节点是否已经访问过了。因此,下面采用两个方法来实现非递归访问。

2.1 实现方式一

通过栈+链表配合,流程如下:

  1. 根节点入栈,然后循环遍历访问栈顶元素。
  2. 每访问一个元素,把该元素插入到链表开头,然后分别把左、右子节点压栈。
  3. 循环1-2步,完成后把链表中的节点顺序输出。

代码实现:

2.2 实现方式二

非递归的后序遍历和前、中序遍历一样,也依赖栈这个数据结构,原理:

  1. 把根节点压栈两次,然后循环判断,当栈不为空的时候,取出栈顶元素。
  2. 把取出的栈顶元素和栈当前的栈顶元素对比,如果相等,则把右子节点和左子节点也分别压入栈两次;如果不相等,则访问当前元素。

压栈两次的作用:判断第几次访问节点,第一次访问到节点的时候要先访问子节点,第二次才是访问自己。

一个特别要注意的地方是:栈是先进后出的,所以在压入左右子节点的时候,要先压入右子节点。

代码实现:

三、递归实现

历史上的今天
二月
9
马谦马谦马谦
  • 本文由 发表于 2020年2月9日13:57:19
  • 转载请务必保留本文链接:https://www.dyxmq.cn/program/algorithms/postorder-in-binary-trees.html
二叉树的中序遍历 数据结构和算法

二叉树的中序遍历

一、中序遍历 中序遍历过程:先访问左子节点,然后访问当前节点,最后访问右子节点。 以下试一次中序遍历过程: 二、非递归实现 非递归方式遍历依赖栈来实现,因为要先访问子节点,然后访问父节点,因此必须要有...
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: