二叉树的非递归后序遍历

BlackMass 发布于2019-08-21 17:08 / 3645人阅读

摘要：后序遍历概念后序遍历指先遍历节点的左子树，再遍历节点的右子树，最后访问节点，按照这种规则不重复地访问树中所有节点的过程。第一次在到达该节点时被使用，第二次在左子树遍历结束后被使用，第三次在右子树遍历结束后使用。

后序遍历 概念

「后序遍历」指先遍历节点的左子树，再遍历节点的右子树，最后访问节点，按照这种规则不重复地访问树中所有节点的过程。

思路

树的结构如下，以变量root保存

// 节点的数据结构
function Node(value) {
  this.value = value
  this.left = null
  this.right = null
}

root {
  value: "A",
  left: {
      value: "B",
      left: {
          value: "D",
          left: {
              value: "H",
              left: null,
              right: {
                  value: "K",
                  left: null,
                  right: null
              }
          },
          right: null
      },
      right: {
          value: "E",
          left: null,
          right: null
      }
  },
  right: {
      value: "C",
      left: {
          value: "F",
          left: {
              value: "I",
              left: null,
              right: null
          },
          right: null
      },
      right: {
          value: "G",
          left: null,
          right: {
              value: "J",
              left: null,
              right: null
          }
      }
  }
}

先遍历节点的左子树，再遍历节点的右子树，最后访问节点。其中一个节点会被使用三次，第一次被用于遍历其左子树，第二次被用于遍历其右子树，第三次被用于访问节点。第一次在到达该节点时被使用，第二次在左子树遍历结束后被使用，第三次在右子树遍历结束后使用。第一次到达该节点可以直接使用该节点，与此同时，需要将节点存入栈中，方便第二次、第三次使用。

代码

const postOrderTraverse = root => {
  let current = root,
    stack = []
  while (current || stack.length !== 0) {
    if (current) {
      stack.push(current) // 存入栈中用于从节点去遍历其右子树
      stack.push(current) // 存入栈中用于访问节点值
      current = current.left // 遍历左子树
    } else {
      current = stack.pop()
      if (current === stack[stack.length - 1]) { // 若栈顶节点和紧随的节点一样，说明是第二次使用该节点
        current = current ? current.right : null // 从节点去遍历其右子树
      } else { // 若栈顶节点和紧随的节点一样，说明是第三次使用该节点
        console.log(current.value) // 访问节点值
        current = null // 使下一次循环进入current不存在的代码片段中，好处理栈顶节点
        // current = stack.pop() 若写成这样，会进入current存在的代码片段，栈顶节点会再次重复入栈
      }
    }
  }
}
postOrderTraverse(binaryTree.root)
// K H D E B I F J G C A

云服务器 GPU云服务器二叉树的遍历非递归二叉树遍历二叉树的存储二叉树的存储结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/89170.html

【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

摘要：在数据结构领域对应树结构来说二叉树是最常用的一种树结构，二叉树具有一个唯一的根节点，也就是最上面的节点。二叉树每个节点最多有两个孩子，一个孩子都没有的节点通常称之为叶子节点，二叉树每个节点最多有一个父亲，根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

ghnor 2019-08-23 16:19 评论0 收藏0
【从蛋壳到满天飞】JAVA 数据结构解析和算法实现-二分搜索树

摘要：在数据结构领域对应树结构来说二叉树是最常用的一种树结构，二叉树具有一个唯一的根节点，也就是最上面的节点。二叉树每个节点最多有两个孩子，一个孩子都没有的节点通常称之为叶子节点，二叉树每个节点最多有一个父亲，根节点是没有父亲节点的。 showImg(https://segmentfault.com/img/remote/1460000018597053?w=1832&h=9943); 前言...

FuisonDesign 2019-08-16 16:04 评论0 收藏0
二叉树的递归遍历（JS实现）

摘要：本文讨论二叉树的遍历，对节点的访问通过打印节点的值体现出来。从二叉树的根节点出发，遍历可分为三个环节访问节点打印节点的值遍历节点的左子树遍历节点的右子树不同环节执行的先后顺序产生了不同的遍历方式。至于二叉树的非递归遍历，且听下回分解。相关概念「树的遍历」指按照一定规则不重复地访问树中所有节点的过程。「访问」指针对节点的操作，如打印节点的值，更新节点的值等。本文讨论二叉树的遍历，...

ethernet 2019-08-21 17:07 评论0 收藏0
树和树的算法

摘要：树和树的算法一树树的概念树英语是一种抽象数据类型或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。一种时间复杂度额外空间复杂度的二叉树的遍历方式，为二叉树的节点个数。树和树的算法一、树 1.1 树的概念树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个...

RaoMeng 2019-08-19 11:08 评论0 收藏0