Landy Blog
0%

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

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

pre-order 的遍歷特性

這邊說明一下 pre-order 的遍歷特性是
先觸碰 parent node ，
接著，先將左邊分支的 node 全部碰完，
最後，再跑右邊分支去碰右邊分支上的 node。

觸碰順序如下圖的小圓圈數字的順序所示
Imgur
pre-order 遍歷的方式很適合在我們想要複製整個 tree 的時候使用。

pre order 實作程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// ...
BST.prototype.depthFirstTraversal = function(iteratorFnc, order) {
  if(order === 'pre-order') iteratorFnc(this.value);                 // 若是 pre-order 先觸碰 parent node
  if(this.left) this.left.depthFirstTraversal(iteratorFnc, order);   // 接著，觸碰 left-side child node 
  if(order === 'in-order') iteratorFnc(this.value);                  // 因為是執行 pre-order ，所以，不會執行這一行
  if(this.right) this.right.depthFirstTraversal(iteratorFnc, order); // 最後，觸碰 right-side child node 
}

const bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(100);
bst.insert(40);
bst.insert(60);
bst.insert(1);
console.log(bst.depthFirstTraversal(getValue, 'pre-order')); // 50 30 1 40 70 60 100

function getValue(value) {
  console.log(value)
}

上面範例創建出來的 binary search tree 長的像下面這樣，碰觸 node 的順序如小圓圈數字的順序
Imgur

Conclusion

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