二叉树与前序遍历、中序遍历、后续遍历

前言

二叉树相关的面试题也是前端面试中非常重要的一部分。那二叉树是什么样的一种结构呢？

二叉树是一种每个Node节点都不超过两个子树的树结构。一个完整的二叉树，每个节点都是由根节点、左节点、右节点组成。

// 定义节点类型
interface TreeNode {
  // 当前节点的值
  value: number;
  // left节点有可能也是个树，也有可能直接是null
  left: TreeNode | null;
  // right节点有可能也是个树，也有可能直接是null
  right: TreeNode | null;
}

// 定义一个二叉树
const binaryTree: TreeNode = {
  value: 5,
  left: {
    value: 3,
    left: {
      value: 2,
      left: null,
      right: null
    },
    right: {
      value: 4,
      left: null,
      right: null
    }
  },
  right: {
    value: 7,
    left: {
      value: 6,
      left: null,
      right: null
    },
    right: {
      value: 8,
      left: null,
      right: null
    }
  }
}      

在二叉树中，如果想遍历所有二叉树的节点，有三种不同的顺序：前序遍历、中序遍历、后序遍历

前序遍历

首先我们要明白什么是前序遍历，是指展示节点的顺序依次为：root -> left -> right。注意，一定要遵守这个规则。

我们从代码上来看一下。

/**
 * @method preOrderTraversal
 * @description 二叉树的前序遍历
 * @param tree TreeNode | null 二叉树
 * @returns void
 */
function preOrderTraversal(tree: TreeNode | null) {
  // 1. 首先输出root节点即根节点
  // 需要注意的时，tree有可能是null，临界条件判断，或者可以说是递归终止的条件
  if (!tree) return;

  // 输出根节点的值
  console.log(tree.value);

  // 2. 输出left节点
  preOrderTraversal(tree.left);

  // 3. 输出right节点
  preOrderTraversal(tree.right);
}      

调用函数，看下输出的结果：

// 5、3、2、4、7、6、8 => root -> left -> right
preOrderTraversal(binaryTree);      

中序遍历

中序遍历的规则是：left -> root -> right

继续上代码：

/**
 * @method preOrderTraversal
 * @description 二叉树的前序遍历
 * @param tree TreeNode | null 二叉树
 * @returns void
 */
function middleOrderTraversal(tree: TreeNode | null) {
  // 临界点判断
  if (!tree) return;

  // 1. 先输出left的值
  middleOrderTraversal(tree.left);

  // 2. 输出root根节点的值
  console.log(tree.value);

  // 3. 输出right的值
  middleOrderTraversal(tree.right);
}      

调用函数，看下输出的结果：

// 2、3、4、5、6、7、8 => left -> root -> right
middleOrderTraversal(binaryTree);      

后序遍历

后序遍历的原则是：left -> right -> root

/**
 * @method postOrderTraversal
 * @description 二叉树的后序遍历
 * @param tree
 * @returns 
 */
function postOrderTraversal(tree: TreeNode | null) {
  // 临界点判断
  if (!tree) return;

  // 1. 先输出left的值
  postOrderTraversal(tree.left);

  // 2. 输出right的值
  postOrderTraversal(tree.right);

  // 3. 输出根节点的值
  console.log(tree.value);
}      

调用函数，看下输出的结果：

// 2、4、3、6、8、7、5 => left -> root -> right
postOrderTraversal(binaryTree);      

结语