二叉樹與前序周遊、中序周遊、後續周遊

前言

二叉樹相關的面試題也是前端面試中非常重要的一部分。那二叉樹是什麼樣的一種結構呢？

二叉樹是一種每個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);      

結語