用 JavaScript 實作樹的遍歷（Tree Traversal）

2021年12月25日 · 閱讀時間約 6 分鐘

阿昇

Software Engineer

（2026/08/18 更新內容）

此篇為舊文章，我已經另外整理資料結構與演算法的筆記，可以參考資料結構與演算法。

預備知識

了解本文內容之前需要具備的 prerequisite：

JavaScript 基礎知識及 ES6 語法
物件導向觀念
Big O Notation
資料結構的基礎理解
遞迴
資料結構 Stack 與 Queue
資料結構 Tree 以及 Binary Search Tree

什麼是 Tree Traversal？

Tree Traversal 指的是走訪 Tree 上的每一個 node，這邊的 tree 指的是所有種類的 tree，包括 Binary Tree、Binary Search Tree (BST) 等。

要走訪（遍歷）一個 Tree 有兩種常見方法：

Breadth First Search
Depth First Search

以下為了方便解釋，就以之前文章實作過的 BST 來講解。

Breadth First Search

有些人也會把這種搜尋方式稱為 Level-order Traversal

BFS

//      10
//   6     15
// 3  8      20

[10, 6, 15, 3, 8, 20]

定義一個 queue 以及一個變數 visited，來儲放已經造訪過的 node 值
把 root 放入 queue
開始 loop queue，當 queue 有值的時候：
- dequeue 一個 node，把這個 node 的值加入 visited
- 檢查該 node 是否有 left child，有的話 enqueue 進 queue 裡
- 檢查該 node 是否有 right child，有的話 enqueue 進 queue 裡
return 用來儲存造訪過的 node 值的變數 visited

class Node {
  constructor(val) {
    this.val = val;
	this.left = null;
	this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
  	this.root = null;
  }

  ...

  BFS() {
    const queue = [];
    const visited = [];
    let checkNode;
    this.root && queue.push(this.root);
    while (queue.length > 0) {
      checkNode = queue.shift();
      visited.push(checkNode.val);
      checkNode.left && queue.push(checkNode.left);
      checkNode.right && queue.push(checkNode.right);
    }
    return visited;
  }
}

Depth First Search

分為

PreOrder
PostOrder
InOrder

以下用 recursion 實作，但也可以用 stack 實作。

PreOrder

//      10
//   6     15
// 3  8      20

[10, 6, 3, 8, 15, 20]

定義一個變數 visited，來儲放已經造訪過的 node 值
定義一個變數 currentNode 並把 root 放在這個變數中
定義一個 helper function，這個 function 會接收一個 node
- 把這個 node 的值加入 visited
- 如果 node 有 left child，則將 left 作為參數 call helper function
- 如果 node 有 right child，則將 right 作為參數 call helper function
return 用來儲存造訪過的 node 值的變數 visited

class Node {
  constructor(val) {
    this.val = val;
	this.left = null;
	this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
  	this.root = null;
  }

  ...

  DFSPreOrder() {
    const visited = [];
    function helper(node) {
      visited.push(node.val);
      node.left && helper(node.left);
      node.right && helper(node.right);
    }
    this.root && helper(this.root);
    return visited;
  }
}

PostOrder

//      10
//   6     15
// 3  8      20

[3, 8, 6, 20, 15, 10]

實作方式和 PreOrder 只差一點，差別在於 PostOrder 是造訪的 node 值在最後才加入

定義一個變數 visited，來儲放已經造訪過的 node 值
定義一個變數 currentNode 並把 root 放在這個變數中
定義一個 helper function，這個 function 會接收一個 node
- 如果 node 有 left child，則將 left 作為參數 call helper function
- 如果 node 有 right child，則將 right 作為參數 call helper function
- 把這個 node 的值加入 visited
return 用來儲存造訪過的 node 值的變數 visited

class Node {
  constructor(val) {
    this.val = val;
	this.left = null;
	this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
  	this.root = null;
  }

  ...

  DFSPostOrder() {
    const visited = [];
    function helper(node) {
      node.left && helper(node.left);
      node.right && helper(node.right);
      visited.push(node.val);
    }
    this.root && helper(this.root);
    return visited;
  }
}

InOrder

//      10
//   6     15
// 3  8      20

[3, 6, 8, 10, 15, 20]

實作方式也和 PreOrder 只差一點，差別在於 InOrder 是造訪完 node left children 後再將值加入

定義一個變數 visited，來儲放已經造訪過的 node 值
定義一個變數 currentNode 並把 root 放在這個變數中
定義一個 helper function，這個 function 會接收一個 node
- 如果 node 有 left child，則將 left 作為參數 call helper function
- 把這個 node 的值加入 visited
- 如果 node 有 right child，則將 right 作為參數 call helper function
return 用來儲存造訪過的 node 值的變數 visited

class Node {
  constructor(val) {
    this.val = val;
	this.left = null;
	this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
  	this.root = null;
  }

  ...

  DFSInOrder() {
    const visited = [];
    function helper(node) {
      node.left && helper(node.left);
      visited.push(node.val);
      node.right && helper(node.right);
    }
    this.root && helper(this.root);
    return visited;
  }
}

總結

最終 Tree Traversal 會是這樣：

class Node {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

class BinarySearchTree {
  constructor() {
    this.root = null;
  }

  ...

  BFS() {
    const queue = [];
    const visited = [];
    let checkNode;
    this.root && queue.push(this.root);
    while (queue.length > 0) {
      checkNode = queue.shift();
      visited.push(checkNode.val);
      checkNode.left && queue.push(checkNode.left);
      checkNode.right && queue.push(checkNode.right);
    }
    return visited;
  }

  DFSPreOrder() {
    const visited = [];
    function helper(node) {
      visited.push(node.val);
      node.left && helper(node.left);
      node.right && helper(node.right);
    }
    this.root && helper(this.root);
    return visited;
  }

  DFSPostOrder() {
    const visited = [];
    function helper(node) {
      node.left && helper(node.left);
      node.right && helper(node.right);
      visited.push(node.val);
    }
    this.root && helper(this.root);
    return visited;
  }

  DFSInOrder() {
    const visited = [];
    function helper(node) {
      node.left && helper(node.left);
      visited.push(node.val);
      node.right && helper(node.right);
    }
    this.root && helper(this.root);
    return visited;
  }
}

重點

Breadth First Search 和 Depth First Search 兩種方法可以用來造訪 Tree 的每個 node，也因此會用來搜尋某個 node。

Breadth First Search (BFS)
- 具有從起點位置（root）開始廣泛搜尋的特性，因此如果目標離 root 很近的話，很快就會找到目標
Depth First Search (DFS)
- 具有從 root 開始一路下探到 leaf 的特性，所以若目標離 root 比較遠的話，則比起 BFS 會更快找到目標
- InOrder 時常搭配 Binary Search Tree (BST) 使用，因為 BST 的特性會讓 InOrder 的呈現出由小排列到大的結果
- PreOrder 的結果可視為 Tree 結構的輸出（copy），可以藉由這個結果來重現同樣結構的 Tree
- PostOrder 常被用來刪除一個 Tree，因為這種搜尋方式是先走訪 Tree 的 leaf，而 tree 的 remove node 是移除沒有 children 的情況最容易處理，所以正好適合 PostOrder 來處理

Ref

Tree Traversals (Inorder, Preorder and Postorder) - GeeksforGeeks

預備知識​

什麼是 Tree Traversal？​

Breadth First Search​

Depth First Search​

PreOrder​

PostOrder​

InOrder​

總結​

重點​

Ref​