二叉树的前序、中序、后序遍历的两种实现

二叉树是数据结构中的基础结构，透彻的了解二叉树理论可以为二叉查找树、B树等数据结构做良好的铺垫，所以对于这种结构一切的基础就是对其遍历的编程实现。今天我们就来说一说二叉树最基础的三种遍历方式：前序遍历、中序遍历、后序遍历。

什么是二叉树？

在介绍遍历前，先为不太懂数据结构的同学们简单介绍一下二叉树的基本规则：有这么一种数据，他除了自身的值以外还包含最多两个子代节点，一个左子节点、一个右子节点。多个这种数据拼接到一块就形成了一颗二叉树，可以参考下面的图形在脑海中想象一下。

用最简单的JavaScript语言描述这个结构可以直接用JSON的格式做成如下效果(后面的文章再单独介绍如何构建一个真正的Tree对象)：

const tree = {
    
  value:'A',
  left:{
    
    value:'B',
    left:{
    
      value:'D',
      left:{
    
        value:'F',

      },
      right:{
    
        value:'G',
        left:{
    
          value:'H'
        },
        right:{
    
          value:'I'
        }
      }
    },
    right:{
    
      value:'E'
    }
  },
  right:{
    
    value:'C',
    left:{
    
      value:'M'
    },
    right:{
    
      value:'N'
    },
  }
}

二叉树的遍历

根据上面的结构分析可以得出结论，仅仅使用单层循环的方式是无法遍历这种树的所有节点数据的，所以如果想要获取或者是遍历到该树的任意节点，那就需要安排些简单的算法了。

最经典的三种二叉树遍历方式有：前序遍历、中序遍历、后序遍历。

前序遍历的思想

前序遍历的规则是从根节点开始，先找到该节点的左子节点，若该左子节点存在子节点则重复该行为，直到找到某一个节点的子节点是边缘节点后，在获取其右子节点，最终逐层返回，走到根节点的右侧。

前序遍历的微观顺序为：节点本身->左子节点->右子节点。

按照最初的图形结构可以将遍历顺序做以下描述，如图所示。

按照前序遍历的思路，从根节点A开始，其遍历的顺序为：ABDFGHIECMN。前序遍历是二叉树遍历的最简单算法，但根据不同的场景前序遍历并不能保证所有情况的节点查找效率都是最高的，这样就衍生出了后面的几种遍历思想。

中序遍历的思想

中序遍历也是一种二叉树的遍历思想，虽然名称叫中序遍历，并不代表可以直接从树节点中找到中间节点开始遍历，其遍历过程依然要从根节点启动。中序遍历的思想主要是从根节点起，优先找到最左侧的左节点，在该节点起进行遍历，然后找到该左节点的父节点，最后找到该父节点的右节点，若右节点有子代元素，则优先找到该右节点的最左侧子节点，进而往复该操作。

所以中序遍历的微观顺序为：左子节点->父节点->右子节点。

依然按照最初的树形结构进行中序遍历的图形演示，如图所示。

根据图中的路径可以得知，中序遍历的结果为：FDHGIBEAMCN。根据中序遍历的图片描述可以得知，虽然中序遍历的结果是需要从最左的子节点开始向右遍历，但并不能直接获取到最左侧子节点，整个过程需要查找到需要的节点才能继续遍历。

后序遍历的思想

后序遍历与中序遍历类似，并不是从根节点进行遍历，但找到起始节点的思路与中序遍历类似。后序遍历的顺序依然是先找到根节点的最左侧子节点，进而找到该节点父节点的右子节点，若该父节点的右子节点并不是叶子结点，则继续找到其最左侧的叶子节点往复下去，直到找到右侧的叶子节点，最后向上找到其父节点直到根节点。

所以后序遍历的微观顺序就是：左子节点->父节点->右子节点。

后序遍历的进行顺序，如图所示。

后序遍历的整个过程，通过图片的描述已经明朗，其顺序为：FHIGDEBMNCA。后序遍历的节点搜索过程与中序遍历类似，但是优先寻找同父节点的右侧子节点，最后寻找父节点。

代码实现三种遍历

递归实现

未知层深的数据结构，在遍历时无法用指定的循环层进行嵌套，所以最直观也是最好理解的解决办法就是通过递归函数的方式进行遍历，递归函数的优势是可读性强，逻辑清晰，所以深受大家喜欢。在二叉树的遍历中，最简单的实现方式也是递归的方式，接下来演示递归函数的代码编写（以JavaScript为例子，基础数据结构仍然采用前面的tree对象作为树）。

前序遍历的递归实现

/** * 前序遍历的递归实现 * @param {Object} node 节点对象 */
function loopFront(node){
    
  // 优先输出根节点
  console.log(node.value)
  // 若存在左子节点则进入左子节点内继续递归
  if(node.left){
    
    loopFront(node.left)
  }
  // 直到左子节点遍历完毕后才能触发右子节点的递归
  if(node.right){
    
    loopFront(node.right)
  }
}
loopFront(tree)

中序遍历的递归实现

/** * 中序遍历的递归实现 * @param {Object} node 节点对象 */
function loopMid(node){
    

  // 若存在左子节点则进入左子节点内继续递归
  if(node.left){
    
    loopMid(node.left)
  }
  // 函数执行到本行时，代表左子节点的递归走到了最后
  // 第一次运行此步骤时输出的是最左子节点，下一次输出的是其父节点
  console.log(node.value)
  // 直到左子节点遍历完毕后才能触发右子节点的递归
  // 遇到有右子节点后进入右节点递归，这样遍实现了左中右的顺序
  if(node.right){
    
    loopMid(node.right)
  }
}
loopMid(tree)

后序遍历的递归实现

/** * 后序遍历的递归实现 * @param {Object} node 节点对象 */
function loopEnd(node){
    

  // 若存在左子节点则进入左子节点内继续递归
  if(node.left){
    
    loopEnd(node.left)
  }

  // 直到左子节点遍历完毕后才能触发右子节点的递归
  // 遇到有右子节点后进入右节点递归，这样遍实现了左中右的顺序
  if(node.right){
    
    loopEnd(node.right)
  }
  // 函数执行到本行时，代表左右子节点的递归走到了最后
  // 第一次运行此步骤时输出的是最左子节点，下一次输出的则是右侧的叶子节点
  console.log(node.value)
}
loopEnd(tree)

循环实现

递归实现前中后遍历顺序通过代码观察会发现特别的容易，只需要在两个if条件的前中后输出节点，就能实现对应顺序的遍历，所以递归遍历二叉树是最常用的手段之一，但是考虑极端情况的话，由于递归本身是通过函数执行栈运行的，在进栈出栈的过程中会消耗一部分性能，并且函数执行栈存在自身深度限制，若真的存在一颗非常大的树会存在栈溢出的情况。这时很多同学就会陷入焦虑，其实解决问题的办法很多，我们仍然可以采用循环的形式将未知深度的树进行遍历。与递归类似的是，若使用循环的方式遍历二叉树，则需要在代码级别定义栈对象来进行层级的保存，这样才能真正意义上实现树的遍历。

前序遍历的while循环实现

// 节点栈对象
let stack1 = []
// 将根节点入栈
stack1.push(tree)
// 当栈的未空时进行循环
while(stack1.length>0){
    
  // 获取栈顶节点
  let node = stack1.pop()
  // 输出节点对象
  console.log(node.value)
  // 将右节点保存进栈
  if(node.right){
    
    stack1.push(node.right)
  }
  // 将左节点保存进栈
  if(node.left){
    
    stack1.push(node.left)
  }
}

中序遍历的while循环实现

// 节点栈对象
let stack2 = []
// 保存根节点对象
let node = tree
// 若节点为空且栈空则退出循环
while(node||stack2.length>0){
    

  if(node){
    
    // 判断对象不为空则将节点进栈
    stack2.push(node)
    // 并将节点指针向左移动
    node = node.left
  }else{
    
    // 若节点为空，则将栈顶取出
    node = stack2.pop()
    // 第一次取出的则是最左子节点
    // 之后便会按照左中右结构取节点
    console.log(node.value)
    // 最后将节点指针向右移动
    node = node.right
  }
}

后序遍历

// 上一次操作的节点对象
let lastNode3 = tree
// 节点栈对象
let stack3 = []
// 保存根节点进栈
stack3.push(tree)
// 当节点栈空则退出循环
while(stack3.length>0){
    
  // 获取栈顶节点（此步骤不要将其出栈）
  let node = stack3[stack3.length-1]

  if(node.left&&node.left!=lastNode3&&node.right!=lastNode3){
    
    // 以左节点为主进行遍历，若该节点存在左子节点
    // 并且该节点的左子节点和右子节点均未被操作过，则进栈
    stack3.push(node.left)
  }else if(node.right&&node.right!=lastNode3){
    
    // 若该不满足第一条件，该节点的右侧子节点存在
    // 并且该节点的右侧子节点并没有被遍历过则将其放入栈中
    stack3.push(node.right)
  }else{
    
    // 若1，2条件均不满足代表该节点没有子节点或涉及节点均被操作
    // 此时输出节点，第一次输出的一定是最左侧节点
    console.log(node.value)
    // 找到目标节点后再将栈顶弹出
    // 并记录当前节点被操作过，这样下次遍历时则会以当前节点的
    // 父节点为主继续向右遍历，并重复下去直到找回根节点
    stack3.pop()
    lastNode3 = node
  }
}

遍历树对工作的帮助

遍历树的算法是很基础的编程手段，在各类树形结构的处理上都十分好用，学习该内容有助于理解属性结构的指针跳动过程，为后续的二叉查找树和B树的结构提供了非常大的帮助。所以树形结构的遍历是一切的基础。比如HashMap底层的红黑树，作为数据库索引的B+树，在使用过程中都会大量应用树形结构的遍历算法。

总结

本篇文章以最基础的遍历树为核心，希望能帮助到刚踏入数据结构学习领域的同学，作者会在后续闲暇时间中继续更新AVL树以及红黑树等结构的创建和操作，若喜欢我的文章，希望大家可以点赞关注加分享。