资讯专栏INFORMATION COLUMN

二叉树的非递归中序遍历

mudiyouyou / 1047人阅读

摘要:中序遍历概念中序遍历指先遍历节点的左子树,再访问节点,最后遍历节点的右子树,按照这种规则不重复地访问树中所有节点的过程。用栈保存经过的待访问的节点,栈顶节点表示正在遍历节点的左子树。同时,说明栈顶节点的左子树遍历结束。

中序遍历 概念

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

思路

图中树的结构如下,以变量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
          }
      }
  }
}

设计函数,传入的参数为树的根root,从根节点出发,遍历所有节点

/**
 * 中序遍历二叉树
 * 传入的参数是二叉树的根
 * @param {Node} root 
 */
function inOrderTraverse(root) {
  let current = root // 从根节点出发
  while (current) { // 找到下个节点,若不存在,则跳出循环,遍历结束
    let nextNode
    // 寻找下个节点
    current = nextNode // 前往下个节点
  }
}

先遍历节点的左子树,再访问节点,最后遍历节点的右子树。故当来到节点,发现其存在左子树时,先遍历其左子树,前往的下个节点就是左子树的根,即当前节点的左孩子,同时将当前节点保存,当其左子树遍历结束后,再访问该节点,并遍历该节点的右子树。用栈保存经过的待访问的节点,栈顶节点表示正在遍历节点的左子树。

function inOrderTraverse(root) {
  let current = root, // 从根节点出发
    stack = [] // 保存待访问的节点
  while (current) { // 找到下个节点,若不存在,则跳出循环,遍历结束
    let nextNode
    if (current.left) { // 当前节点存在左子树
      stack.push(current) // 保存当前节点,当其左子树遍历结束后,再访问该节点
      nextNode = current.left // 前往当前节点的左孩子,遍历当前节点的左子树
    }
    // 未完待续
    current = nextNode // 前往下个节点
  }
}

当节点仅存在右子树时,因为其无左子树,所以直接访问节点,并前往节点的右孩子,开始遍历其右子树。

function inOrderTraverse(root) {
  let current = root, // 从根节点出发
    stack = [] // 保存待访问的节点
  while (current) { // 找到下个节点,若不存在,则跳出循环,遍历结束
    let nextNode
    if (current.left) { // 当前节点存在左子树
      stack.push(current) // 保存当前节点,当其左子树遍历结束后,再访问该节点
      nextNode = current.left // 前往当前节点的左孩子,遍历当前节点的左子树
    } else if (!current.left && current.right) { // 仅存在右子树
      console.log(current.value) // 无左子树,直接访问节点
      nextNode = current.right // 开始遍历其右子树
    }
    // 未完待续
    current = nextNode // 前往下个节点
  }
}

当节点无子树遍历,直接访问节点。同时,说明栈顶节点的左子树遍历结束。栈顶节点出栈,访问节点,开始遍历其右子树。若节点无右子树,说明栈中新的栈顶节点的左子树遍历结束。栈顶节点出栈,访问节点,开始遍历其右子树。如此循环直至节点含右子树。

function inOrderTraverse(root) {
  let current = root, // 从根节点出发
    stack = [] // 保存待访问的节点
  while (current) { // 找到下个节点,若不存在,则跳出循环,遍历结束
    let nextNode
    if (current.left) { // 当前节点存在左子树
      stack.push(current) // 保存当前节点,当其左子树遍历结束后,再访问该节点
      nextNode = current.left // 前往当前节点的左孩子,遍历当前节点的左子树
    } else if (!current.left && current.right) { // 仅存在右子树
      console.log(current.value) // 无左子树,直接访问节点
      nextNode = current.right // 开始遍历其右子树
    } else { // 节点无子树
      console.log(current.value) // 访问节点
      let pop = stack.pop() // 栈顶节点的左子树遍历结束,栈顶节点出栈
      while (pop && !pop.right) { // 若出栈节点不含右子树
        console.log(pop.value) // 访问出栈的节点
        // 此时栈中新的栈顶节点的左子树遍历结束
        pop = stack.pop() // 栈顶节点出栈
      } // 直到栈空或弹出含右子树的节点
      if (pop) { // 含右子树的节点
        console.log(pop.value) // 访问节点
        nextNode = pop.right // 前往其右孩子,开始遍历其右子树
      } else { // 栈空
        nextNode = null // 找不到下个节点,循环结束
      }
    }
    current = nextNode // 前往下个节点
  }
}
代码

整理后代码如下

/**
 * 中序遍历二叉树
 * 传入的参数是二叉树的根
 * @param {Node} root 
 */
const inOrderTraverse = root => {
  let current = root,
    stack = []
  while (current) {
    if (current.left) {
      stack.push(current)
      current = current.left
    } else if (!current.left && current.right) {
      console.log(current.value)
      current = current.right
    } else {
      console.log(current.value)
      let pop = stack.pop()
      while (pop && !pop.right) {
        console.log(pop.value)
        pop = stack.pop()
      }
      pop && console.log(pop.value)
      current = pop ? pop.right : null
    }
  }
}
inOrderTraverse(binaryTree.root)
// H K D B E A I F C G J

其实没那么复杂,别人家代码

const inOrderTraverse = root => {
  let current = root,
    stack = []
  while (current || stack.length !== 0) {
    if (current) {
      stack.push(current)
      current = current.left // 遍历左子树
    } else {
      current = stack.pop()
      current && console.log(current.value) // 访问节点
      current = current ? current.right : null // 遍历右子树
    }
  }
}
inOrderTraverse(binaryTree.root)
// H K D B E A I F C G J

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

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

相关文章

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

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

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

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

    FuisonDesign 评论0 收藏0
  • 二叉树的递归遍历(JS实现)

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

    ethernet 评论0 收藏0
  • 树和树的算法

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

    RaoMeng 评论0 收藏0

发表评论

0条评论

mudiyouyou

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<