• Home
  • home > theory > algorithm > Tree2Graph >

    讲透学烂二叉树(三)：二叉树的遍历图解算法步骤及JS代码

    Author：zhoulujun Date：

    二叉树的遍历是指不重复地访问二叉树中所有结点，主要指非空二叉树。二叉树的遍历分为深度优先遍历（先序遍历、中序遍历、后序遍历）和广度优先遍历 （层次遍历），遍历方法图解看起来更易理解

    二叉树的遍历是指不重复地访问二叉树中所有结点，主要指非空二叉树，对于空二叉树则结束返回。

    二叉树的遍历分为

    • 深度优先遍历

      • 先序遍历：根节点->左子树->右子树（根左右），有的叫：前序遍历

      • 中序遍历：左子树->根节点->右子树（左根右）

      • 后序遍历：左子树->右子树->根节点（左右根）

    • 广度优先遍历

      • 层次遍历：

    1590962-20190306170951841-1886726002.jpg

    二叉树-深度的优先遍历-图解

    深度优先，前、中、后遍历顺序，就是组合[根左右]，移动根的位置，根左右、左根右、左右根，但是我即使代码会写了，还是搞不明白这个根左右与遍历的关系毛线头在哪里，特别是中序遍历的左根右，

    博主YuXi_0520的图解，应该是我看过最易懂的。这里盗图贴一下

    先序遍历（DLR）

    先序遍历可以想象成，小人从树根开始绕着整棵树的外围转一圈，经过结点的顺序就是先序遍历的顺序

    二叉树先序遍历流程图解

    让我们来看下动画，和小人儿一起跑两遍就记住啦，记住是绕着外围跑哦   

    二叉树先序列遍历-gif动画演示    二叉树先序遍历 小人动画演示

    先序遍历结果：ABDHIEJCFKG

    二叉树先序遍历-js代码实现

    递归实现—二叉树先序遍历

    根 - 左 - 右递归

    判断根结点是否为空，为空则返回null；否则取结点的值，然后去左、右结点的值

    /**
 * @description 前序遍历 =>1.访问根节点； 2.访问左子树； 3.访问右子树
 * @param node {Node} 遍历的树
 */
preOrderTraverse (node = this.tree) {
    // 数组存储数遍历值
    let backs = []

    // 递归，
    function tempFunction (node) {
        if (node.data !== null) {
            // 先取根结点
            backs.push(node.data)
            // 如果存在左结点，取左节点的值
            node.leftChild && tempFunction(node.leftChild)
            // 如果存在右结点，取右结点值
            node.rightChild && tempFunction(node.rightChild)
        }
    }

    tempFunction(node)
    return backs
}


    非递归-二叉树先序遍历

    取结点的值，然后将左、右结点压如栈

    function preOrderTraverse2 (node = this.tree) {
  let backs = []
  if (!node) {
    return backs
  }
  let stack = [node]
  while (stack.length) {
    // 取出最后一个结点，对这个结点进行遍历
    let root = stack.pop()
    backs.push(root.data)
    // 因为stack .pop，所以先存入右结点
    root.rightChild && stack.push(root.rightChild)
    root.leftChild && stack.push(root.leftChild)
  }
  return backs
}

    下面代码应该更容易理解

    如果结点存在左结点，取值，然后存入栈中，直至没有左结点是叶子，再取右边

    function preOrderTraverse3 (node = this.tree) {
  let backs = []
  if (!node) {
    return backs
  }
  let currentNode = node
  let stack = [node]
  while (stack.length) {
    if(currentNode){
      backs.push(currentNode.data)
      stack.push(currentNode)
      currentNode=currentNode.leftChild
    }else {
      currentNode = stack.pop()
      currentNode = currentNode.rightChild
    }
  }
  return backs
}


    中序遍历（LDR）

    中序遍历可以想象成，按树画好的左右位置投影下来就可以了

    二叉树-中序遍历-gif动图演示

    下面看下投影的过程动画，其实就是按左右顺序写下来就行了

    中序遍历结果：HDIBEJAFKCG

    二叉树中序遍历-JavaScript代码实现

    递归实现-二叉树中序遍历
    /**
 * @description 中遍历 =>左右根
 * @param node {Node} 遍历的树
 */
function inOrderTraverse (node = this.tree) {
    // 数组存储数遍历值
    let backs = []

    // 递归，
    function tempFunction (node) {
        if (node.data !== null) {
            // 如果存在左结点，取左节点的值
            node.leftChild && tempFunction(node.leftChild)
            // 取根结点
            backs.push(node.data)
            // 如果存在右结点，取右结点值
            node.rightChild && tempFunction(node.rightChild)

        }
    }

    tempFunction(node)
    return backs
}


    非递归实现-二叉树中序遍历
    function inOrderTraverse2(node){
  let backs = []
  if(!node){
    return backs
  }
  let stack = [node]
  let currentNode = node
  while(stack.length){
    if(currentNode){
      stack.push(currentNode)
      currentNode = currentNode.leftChild
    }else {
      currentNode = stack.pop()
      backs.push(currentNode.data)
      currentNode = currentNode.rightChild
    }
  }
}


    后序遍历（LRD）

    后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的（从左到右，剪最底下的叶子结点）。

    就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄），就把它剪下来，组成的就是后序遍历了。

    跟之前先序遍历绕圈的路线是一样的(先序遍历，是遇到结点，就push到数组），但是后续遍历是：递归：先取左叶结点（没有就跳过），再取右叶子结点


    二叉树-后续遍历二叉树-后续遍历-gif图

    后序遍历结果：HIDJEBKFGCA

    二叉树后续遍历-JavaScript代码实现

    递归实现—二叉树后续遍历
    /**
 * @description 后序遍历 =>左根右
 *  1.访问左子树。（先访问左子树中的左子树，再访问左子树中的右子树）
 *  2.访问右子树。（先访问右子树中的左子树，再访问右子树中的右子树）
 *  3.访问根
 * @param node {Node} 遍历的树
 */
postOrderTraverse (node) {
    // 数组存储数遍历值
    let backs = []

    // 递归，
    function tempFunction (node) {
        if (node.data !== null) {
            // 如果存在左结点，取左节点的值
            node.leftChild && tempFunction(node.leftChild)
            // 如果存在右结点，取右结点值
            node.rightChild && tempFunction(node.rightChild)
            // 最后取根结点
            backs.push(node.data)
        }
    }

    tempFunction(node)
    return backs
}

    非递归实现—二叉树后续遍历

    function postOrderTraverse2 (node){
    let backs = []
    if(!node){
        return backs
    }
    let stack  = [node]
    while(stack.length){
        let root = stack.pop()
        backs.push(root.data)
        root.leftChild&&stack.push(root.leftChild)
        root.rightChild&&stack.push(root.rightChild)
    }
    return  backs
}
    非递归实现2—二叉树后续遍历
    function postOrderTraverse2 (node) {
    let backs = []
    if (!node) {
        return backs
    }
    let stack = []
    let currentNode = node
    while (stack.length||currentNode) {
        if (currentNode) {
            stack.push(currentNode)
            backs .unshift(currentNode.data)
            currentNode = currentNode.rightChild
        } else {
            currentNode = stack.pop()

        }
    }
    return backs
}
    非递归实现3—二叉树后续遍历
    postOrderTraverse3 (node) {
    let backs = []
    if (!node) {
        return backs
    }
    let stack = [node]
    while (stack.length) {
        let currentNode = stack.pop()
        backs.unshift(currentNode.data)
        currentNode.leftChild && stack.push(currentNode.leftChild)
        currentNode.rightChild && stack.push(currentNode.rightChild)
    }
    return backs
}
    非递归实现4—二叉树后续遍历
    postOrderTraverse4 (node) {
    let backs = []
    if (!node) {
        return backs
    }
    let stack = [node]
    let currentNode = node
    let visitedNode = null
    while (stack.length) {
        if (currentNode) {
            stack.push(currentNode)
            currentNode = currentNode.leftChild
        } else {
            currentNode = stack[stack.length - 1]
            if (currentNode.rightChild && currentNode.rightChild !== visitedNode) {
                currentNode = currentNode.rightChild
            } else {
                backs.push(currentNode.data)
                visitedNode = currentNode
                stack.pop()
                currentNode = null
            }
        }
    }
    return backs
}


    先后、中序、后续总结

    几乎所有二叉树的题目都是一套这个框架就出来了：

    递归


    postOrderTraverse (node) {
  // 数组存储数遍历值
  let backs = []

  // 递归，
  function tempFunction (node) {
    if (node.data !== null) {
      // 先序  backs.push(node.data)
      node.leftChild && tempFunction(node.leftChild)
      // 中序  backs.push(node.data)
      node.rightChild && tempFunction(node.rightChild)
      // 后续  backs.push(node.data)
    }
  }

  tempFunction(node)
  return backs
}
    核心架构
    function traverse (root) {
    // 前序位置
    traverse(root.left);
    // 中序位置
    traverse(root.right);
    // 后序位置
}


    遍历

    先序遍历可以这么写

    function  traverse (node = this.tree) {
  let backs = []
  if (!node) {
    return backs
  }
  let stack = [node]
  while (stack.length) {
    // 取出最后一个结点，对这个结点进行遍历
    let root = stack.pop()
    backs.push(root.data)
    // 先序
    /* root.rightChild && stack.push(root.rightChild)
    root.leftChild && stack.push(root.leftChild) */
    // 后续
    /* root.leftChild&&stack.push(root.leftChild)
    root.rightChild&&stack.push(root.rightChild) */
  }
  return backs
}

    核心在于入栈时机。你发现中序并没有这样写？为什么中序遍历不能采用同样的代码结构呢？

    因为中序遍历要采用上面同样的代码结构，如果是新手，可以忽略下面内容，看完中序与后续遍历，再来回顾下面的内容。

    在先序遍历和后续遍历中，我们使用栈来存储待访问的结点，而不需要显式地设置一个当前结点。这是因为在这两种遍历方式中，我们可以通过栈顶元素来访问当前结点，而不需要显式地设置一个指针来存储当前结点。

    • 在先序遍历中，我们首先访问当前结点，然后将其右子结点和左子结点依次入栈。在后续遍历中，我们将当前结点的左子结点和右子结点依次入栈，然后访问当前结点。在这两种遍历方式中，我们可以通过栈顶元素来访问当前结点，而不需要显式地设置一个指针来存储当前结点。

    • 在中序遍历中，我们需要在访问当前结点之前将其所有左子结点入栈，并在访问当前结点之后访问其右子结点。这个过程需要一个指针来存储当前结点，以便在遍历过程中正确地访问左子结点和右子结点。因此，在中序遍历的实现中，我们需要设置一个当前结点指针。

    中序遍历要求我们按照左-根-右的顺序访问节点。为了实现这一点，使用current变量追踪当前节点，简单说，current变量使我们能够追踪到达最左侧节点的过程，并在之后正确地转到右子节点。这是实现中序遍历特定顺序（左-根-右）的关键，而这种顺序在先序和后序遍历的实现中并不是通过类似的方式来实现的。


    都用中序的代码结构来看

    先序


    while (stack.length) {
  if(currentNode){
    backs.push(currentNode.data)
    stack.push(currentNode)
    currentNode=currentNode.leftChild
  }else {
    currentNode = stack.pop()
    currentNode = currentNode.rightChild
  }
}
    中序


    while(stack.length){
  if(currentNode){
    stack.push(currentNode)
    currentNode = currentNode.leftChild
  }else {
    currentNode = stack.pop()
    backs.push(currentNode.data)
    currentNode = currentNode.rightChild
  }
}
    后续
    while (stack.length||currentNode) {
  if (currentNode) {
    backs.unshift(currentNode.data)
    stack.push(currentNode)
    currentNode = currentNode.rightChild
  } else {
    currentNode = stack.pop()
  }
}

    差异蛮大，去思考下，为什么怎么写？



    二叉树-广度优先遍历-图解

    这个只有层序遍历

    层序遍历

    层序遍历太简单了，就是按照一层一层的顺序，从左到右写下来就行了。

    二叉树-广度优先-层序遍历

    层序遍历结果：ABCDEFGHIJK

    二叉序层序遍历-JavaScript代码实现

    /**
 * @description 中遍历 =>左右根
 * @param node {Node} 遍历的树
 */
inOrderTraverse (node = this.tree) {
    // 数组存储数遍历值
    let backs = []

    // 递归，
    function tempFunction (node) {
        if (node.data !== null) {
            // 如果存在左结点，取左节点的值
            node.leftChild && tempFunction(node.leftChild)
            // 取根结点
            backs.push(node.data)
            // 如果存在右结点，取右结点值
            node.rightChild && tempFunction(node.rightChild)

        }
    }

    tempFunction(node)
    return backs
}

    不知道通过这种方式，有没有觉得闭着眼睛都能写出前序、中序、后序 、层序了呀，不过这只是为了大家好理解，我想出的一种形象思维，为了用代码实现，我们还需要具体了解一下前序、中序、后序遍历。

    真正理解三种遍历

    还记得我们先序和后序遍历时候跑的顺序么？按照这个顺序再跑一次，就是围着树的外围跑一整圈。

    让我们来理解一下绕着外围跑一整圈的真正含义是：遍历所有结点时，都先往左孩子走，再往右孩子走。

    二叉树-先序与后续遍历流程图

    观察一下，你有什么发现？

    有没有发现，除了根结点和空结点，其他所有结点都有三个箭头指向它。

    • 一个是从它的父节点指向它，

    • 一个是从它的左孩子指向它

    • 一个是从它的右孩子指向它。

    一个结点有三个箭头指向它，说明每个结点都被经过了三遍。

    • 一遍是从它的父节点来的时候，

    • 一遍是从它的左孩子返回时，

    • 一遍是从它的右孩子返回时。

    其实我们在用递归算法实现二叉树的遍历的时候，不管是先序中序还是后序，程序都是按照上面那个顺序跑遍所有结点的。

    先序中序和后序唯一的不同就是，在经过结点的三次中，哪次访问（输出或者打印或者做其他操作）了这个结点。有点像大禹治水三过家门，他会选择一次进去。

    • 先序遍历顾名思义，就是在第一次经过这个结点的时候访问了它。就是从父节点来的这个箭头的时候，访问了它。

    • 中序遍历也和名字一样，就是在第二次经过这个结点的时候访问了它。就是从左孩子返回的这个箭头的时候，访问了它。

    • 后序遍历，就是在第三次经过这个结点的时候访问了它。就是从右孩子返回的这个箭头的时候，访问了它。

    怎么样，这样有没有很好的理解？

    其实不管是前序中序还是后序，在程序里跑的时候都是按照同样的顺序跑的，每个结点经过三遍，第几遍访问这个结点了，就叫什么序遍历。

    当我们脑子里有这个概念的时候， 再去看实现代码就很好理解了，下一篇博文我会贴出和讲解具体的实现代码。

    如果递归分治来理解前、中、后遍历与根左右、左根右、左右根的关系，就是按照那个跑路图，对每个最底层的子结点[前、中、后]对应[根左右、左根右、左右根]顺序来处理。

    二叉树前序、中序、后序遍历相互求法

    已知二叉树的广度优先遍历-层序遍历数组，是可以完全还原二叉树结构，但是

    已知二叉树前序、中序、后序中的一种排序数组，是无法求出二叉树结构的。但是知道前序、中序、后序中的中序和前序或后序数组两种也可以还原二叉树，为何可以推出二叉树的数据结构。

    前序根结点在最前，后续根结点在最后，如果已知前序或者后续，则中序中根结点两边的元素分布为根结点的左边结点和右边结点元素。具体操作如下：

    已知前序、中序遍历，求后序遍历

    • 前序遍历=ABGDECFH

    • 中序遍历=GBEDAFCH

    构建二叉树步骤：

    1. 根据前序遍历的特点，我们知道根结点root为A；

    2. 观察中序遍历GBEDAFCH。其中root节点A的左侧GBED必然是root的左子树，右侧FCH必然是root的右子树。同时，这个也分别是左子树和右子树的中序遍历的序列；

    3. 在前序遍历遍历完根节点后，接着执行前序遍历左子树，注意，是前序遍历，什么意思？就是把左子树当成一棵独立的树，执行前序遍历，同样先访问左子树的根，第2步我们已经知道左子树是BGDE（前序遍历序列）了，由此可以得到，左子树的根是B，那么在这一步得到左子树的根是B；

    4. 从第2步得到的中序遍历的节点序列中，找到B，发现B左边只有一个G，说明B的左子树只有一个叶子节点，B的右边呢？我们可以得到B的右子树有ED，再看前序遍历的序列，发现D在前，也就是说，D是先前序遍历访问的，则得到E是D的左子树，只有一个叶子节点。到这里，我们可以得到这棵树的根结点和左子树的结构了，如下图一

    5. 接着看右子树，在第2步的时候已经知道右子树是FCH这三个节点，那么先看前序遍历的序列，先出现的是C，那么C就是右子树的根结点，看右子树的中序遍历为FCH，所以F和H就分别是它的左子树和右子树，因此，右子树的结构就出来了，如下图二

    二叉树线序与中序，还原二叉树

    已知中序、后序遍历，求前序遍历

    • 中序遍历：GBEDAFCH

    • 后序遍历：GEDBFHCA

    同理，步骤和上面的类似，还是得先找出根结点，由后序遍历的特点，根结点root在最后，所以根结点为A，再由中序遍历可以知道左子树和右子树分别为GBED、FCH；再按照上面的步骤递归分别求出左右子树即可得解。

    已知前序、后序遍历，求中序遍历

    已知前序、中序或者中序、后序都可以唯一确定一棵二叉树，但是已知前序、后序是无法唯一确定一棵二叉树的，解不唯一。


    关于算法相关的详细代码，查看https://github.com/zhoulujun/algorithm

    参考文章：

    理解二叉树的三种遍历--前序、中序、后序 +层序（简明易懂）https://blog.csdn.net/weixin_44032878/article/details/88070556

    js数据结构-二叉树（二叉堆） https://segmentfault.com/a/1190000017761929 （推荐阅读-理解堆排序-堆化操作）

    二叉树前序、中序、后序遍历相互求法 https://blog.csdn.net/qq_34154570/article/details/82700094

    JavaScript 二叉树遍历专题：算法描述与实现 https://zhuanlan.zhihu.com/p/27307626

    JS - 二叉树算法实现与遍历  (更新中...) https://www.cnblogs.com/padding1015/p/7729988.html

    二叉树的遍历（前序、中序、后序、已知前中序求后序、已知中后序求前序） https://www.cnblogs.com/lanhaicode/p/10390147.html

    面试BAT 却被二叉树秒杀？20 道题帮你一举拿下二叉树算法题 https://zhuanlan.zhihu.com/p/88361872


    转载本站文章《讲透学烂二叉树(三)：二叉树的遍历图解算法步骤及JS代码》,
    请注明出处：https://www.zhoulujun.cn/html/theory/algorithm/TreeGraph/8283.html

    收藏
    上一篇：讲透学烂二叉树(二)：图中树的定义&各类型树的特征分析
    下一篇：讲透学烂二叉树(四)：二叉树的存储结构—建堆-搜索-排序
    延伸阅读：