Landy Blog
0%

資料結構-Binary Search Tree - Depth First Traversal - Post Order

發表於 更新於 分類於 ，
紀錄 Binary Search Tree 的 Depth First Traversal 在 Post order 的狀態下是怎麼遍歷的

post-order 的遍歷特性

  1. 先遍歷到整個 tree 的最左邊且最末端的 node(i.e. 值最小的 node)。
  2. 對 step 1 這個最左邊的 node 執行傳入的 iteratorFnc，
    再來對這個最左邊 node 所隸屬的 sub tree 的 right-side child node 執行傳入的 iteratorFnc。
  3. 最後再對 step 2 這個 sub tree 的 parent node 執行傳入的 iteratorFnc。
  4. 接著，就是一直往上對不同層的 sub tree 不停地執行 step 1 - step 3 這個流程的操作。

由此我們可以知道 post-order ，
會先觸碰 left-side child node ，
再碰 right-side child node，
最後才碰 parent node。

這樣子先處理 sub tree 的所有 child node 的特性，很適合在刪除 tree 的操作時使用，因為我們可以確保當 child node 都被刪除後，才會往 parent node 繼續做刪除的動作。

程式碼的寫法如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// ...
BST.prototype.depthFirstTraversal = function(iteratorFnc, order) {
  if(order === 'pre-order') iteratorFnc(this.value);
  if(this.left) this.left.depthFirstTraversal(iteratorFnc, order);
  if(order === 'in-order') iteratorFnc(this.value);
  if(this.right) this.right.depthFirstTraversal(iteratorFnc, order);
  if(order === 'post-order') iteratorFnc(this.value); // 就加這一行判斷 order 是否為 post-order 進去
}

const bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(100);
bst.insert(40);
bst.insert(60);
bst.depthFirstTraversal(getValue, 'post-order'); // 40 30 60 100 70
function getValue(value) {
  console.log(value);
}

Conclusion

  • post order 執行傳入 function 的次序為 left node -> right node -> parent node。
  • pre order 這種執行特性，適合用在刪除 tree 的需求。