二叉树的递归遍历（JS实现）

作者: nbb3210 | 来源:发表于2017-10-18 10:55 被阅读211次

算法之二叉树
数据结构之二叉树
深入浅出二叉树遍历的非递归算法 2019-11-15（未经允许，
Java二叉树的遍历
二叉树，非递归法
python实现二叉树
总结
Tree
二叉树的三种深度优先遍历算法与思路
二叉树前序、中序、后序遍历（递归）

前序遍历

图1 前序遍历

图1展现了前序遍历的整个过程，图中树的结构用代码表示如下

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: null
          },
          right: {
              value: 'I',
              left: null,
              right: null
          }
      },
      right: {
          value: 'E',
          left: null,
          right: null
      }
  },
  right: {
      value: 'C',
      left: {
          value: 'F',
          left: null,
          right: null
      },
      right: {
          value: 'G',
          left: null,
          right: null
      }
  }
}

我们要设计一个函数，用于遍历二叉树，传入的参数是二叉树的根节点，函数会先访问节点（打印节点的值），再遍历节点的左子树，最后遍历节点的右子树。
上述代码翻译成代码片段就是

/**
 * 函数的作用是遍历二叉树
 * 传入的参数是表示二叉树的根节点
 * @param {any} root 
 */
function preOrderTraverse(root){
  console.log(root.value) // 访问节点（打印节点的值）
  ... // 遍历节点的左子树
  ... // 遍历节点的右子树
}

... 处应该是遍历节点的左，右子二叉树的代码。遍历二叉树不正是这个函数的作用吗？故想到了递归

function preOrderTraverse(root){
  console.log(root.value) // 访问节点（打印节点的值）
  preOrderTraverse(root.left) // 遍历节点的左子树
  preOrderTraverse(root.right) // 遍历节点的右子树
}

添加递归的终止条件，即访问到叶节点就停止调用函数

const preOrderTraverse = root => {
  console.log(root.value) // 访问节点（打印节点的值）
  root.left && preOrderTraverse(root.left) // 若节点的左子树存在，则遍历节点的左子树
  root.right && preOrderTraverse(root.right) // 若节点的右子树存在，则遍历节点的右子树
}
preOrderTraverse(root)
// A B D H I E C F G

举一反三

中序遍历

const inOrderTraverse = root => {
  root.left && inOrderTraverse(root.left) // 若节点的左子树存在，则遍历节点的左子树
  console.log(root.value) // 访问节点（打印节点的值）
  root.right && inOrderTraverse(root.right) // 若节点的右子树存在，则遍历节点的右子树
}
inOrderTraverse(root)
// H D I B E A F C G

后序遍历

const postOrderTraverse = root => {
  root.left && postOrderTraverse(root.left) // 若节点的左子树存在，则遍历节点的左子树
  root.right && postOrderTraverse(root.right) // 若节点的右子树存在，则遍历节点的右子树
  console.log(root.value) // 访问节点（打印节点的值）
}
postOrderTraverse(root)
// H I D E B F G C A