Landy Blog
0%

資料結構-Binary Search Tree - Breath First Traversal - part 2

發表於 更新於 分類於 ，
紀錄 Binary Search Tree 的 Breath First Traversal 的實作

Breath First Traversal 的程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// ...
BST.prototype.breathFirstTraversal = function(iteratorFnc) {
  const queue = [this];
  while(queue.length) {
    const currentNode = queue.shift();
    iteratorFnc(currentNode);
    if(currentNode.left) iteratorFnc(currentNode.left);
    if(currentNode.right) iteratorFnc(currentNode.right);
  }
}

const bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(100);
bst.insert(40);
bst.breathFirstTraversal(getValue); // 50 30 70 40 100

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

這邊說明 breathFirstTraversal 的程式碼裡面的作用為何

1
2
3
4
const queue = [this];
// 這個陣列會被稱作 queue 的原因為，我們接下來對待此陣列的元素的操作都是 FIFO(first in first out)，
// 就是 queue 對待元素的處理方式，所以，才會取名為 queue。
// 而寫在陣列裡的 this 就是整個 Binary Search tree 的第一個 node，我們必須以它為起點，才有辦法往下進行 breathFirstTraversal 。
1
2
3
4
5
6
while(queue.length) { // 這一行是代表當 queue 內沒有元素之後，就不再執行這個迴圈
  const currentNode = queue.shift(); // 取出陣列裡的第一個元素，並把它從陣列裡面移除
  iteratorFnc(currentNode); // 將當前取出來的 node 傳入要執行的 function 裡
  if(currentNode.left) queue.push(currentNode.left); // 若當前取出來的 node 有左 node 則將其塞入 queue
  if(currentNode.right) queue.push(currentNode.right); // 若當前取出來的 node 有右 node 則將其塞入 queue
}

具象化程式碼的執行過程

用圖形具象化上面 while 迴圈裡的程式碼執行過程

step 1.
將 node 50 塞入 queue 中，就是 queue = [this] 的這個 this 指向的 node。
Imgur

step 2.
將 node 50 從 queue 取出來，並傳入 iteratorFnc 並將 node 50 的 left-side node 和 right-side node 塞入 queue 裡，所以，node 30 和 node 70 被塞入 queue。
Imgur

step 3.
將 node 30 從 queue 取出來，並傳入 iteratorFnc 並將 node 30 的 left-side node 和 right-side node 塞入 queue 裡，所以， node 40 被塞入 queue。
Imgur

step 4
將 node 70 從 queue 取出來，並傳入 iteratorFnc 並將 node 70 的 left-side node 和 right-side node 塞入 queue 裡，所以， node 100 被塞入 queue。
Imgur

step 5
將 node 40 從 queue 取出來，並傳入 iteratorFnc 並將 node 40 的 left-side node 和 right-side node 塞入 queue 裡，所以， 沒有任何 node 被塞入 queue。
Imgur

step 6
將 node 100 從 queue 取出來，並傳入 iteratorFnc 並將 node 100 的 left-side node 和 right-side node 塞入 queue 裡，所以， 沒有任何 node 被塞入 queue。
Imgur

step 7 結束，整個 tree 的 node 都被遍歷過了。

Conclusion

  • 知道如何撰寫 breathFirstTraversal 程式碼。
  • breathFirstTraversal 是以水平方向的方式遍歷，不是像 depthFirstTraversal 先從最末端的 node 來執行。