Landy Blog
0%

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

發表於 更新於 分類於 ，
紀錄 Binary Search Tree 的 Depth First Traversal 運行的過程，並且在 In order 的狀態下是怎麼遍歷的

Depth First Traversal 在幹嘛?

透過使用 Depth First Traversal 可以將傳入的 function 都運行到 tree 裡的每一個 node 上，並且我們可以決定要 node 以最小值到最大值的惡續來執行傳入的 function。

Depth First Traversal 方法的特性:

  • 會跑過 tree 裡面的所有 node (i.e. tree 裡有 100 個 node，則這 100 個 node 都會被碰到)。
  • 會對每一個被遍歷到的 node 執行傳入的 function
  • 在完成遍歷某個分支上的 node 之前，不會轉到其他分支上做遍歷，而這個特性，也是為什麼這個方法叫做 depth first traversal 的原因，因為會先跑到 tree 裡面值最小的 node，也就是 tree 的最末端的 node。

Depth First Traversal - In Order 的遍歷順序:

In Order 的遍歷順序為: 從最小到最大。
所以，會先碰到 tree 裡的最左邊且最末端(i.e. 值最小)的 node。
接著，再往上碰 parent node 的右邊的 child node。

JS 執行程式碼的順序與特性

當你在推導 depthFirstTraversal 執行的過程時，
請記得 JS 一次只執行一行程式碼，並且執行的順序是由上而下這樣子的特性去推導整個執行的過程。

這邊舉個小範例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function fncA(fnc) {
  fnc();
}

function fncB() {
  console.log('goal!!!');
}

function main() {
  fncA(fncB);
  console.log('the end!!!');
}

// --- 執行結果為 ---
// goal!!!
// the end!!!

由上面的小範例可以知道 JS 一次只會執行一行程式碼，
所以，當 JS 遇到 main function 裡面的 fncA 那一行的時候，
會去執行 fncA 裡面的東西，
又遇到 fnc()，就會去執行 fnc 的內容，
而傳入的 fnc 就是 fncB ，所以，會去執行 fncB 的內容。

最後 fncB 執行完畢，call stack 把 fncB 去除，接著， fncA 裡面也沒有要執行的內容，所以，把 fncA 從 stack 裡面移除。
接著，再執行 console.log('the end!!!') 這一行。
所以，最終執行的結果順序才會是 goal!!! → the end!!!。

Depth First Traversal 執行的過程

假設 DFT 的 tree 節點長的像下面這樣:
Imgur
depth first traversal 程式碼如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// ...
BST.prototype.depthFirstTraversal = function(iteratorFnc, order) {
  if(this.left) this.left.depthFirstTraversal(iteratorFnc, order);
  if(order === 'in-order') iteratorFnc(this.value);
  if(this.right) this.right.depthFirstTraversal(iteratorFnc, order);
}

const bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(40);
bst.insert(100);
bst.insert(1);
bst.depthFirstTraversal(log, 'in-order'); // 1 30 40 70 100 - 由小到大被呈現

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

上面的 depthFirstTraversal 函式遍歷的過程，程式碼執行的順序如下圖的藍底的羅馬數字順序
Imgur

以下是函式在 call stack 的執行順序

Conclusion

  • 知道了 Depth First Traversal 方法的特性
  • 知道了 Depth First Traversal in order 遍歷 node 的大小順序為何
  • 知道了 Depth First Traversal 在遍歷的時候， JS 一次只執行一行程式碼且是由上而下執行的特色是怎麼展現影響遍歷的順序。
  • Depth First Traversal - in order 執行的結果可以以最小至最大的次序呈現。