Landy Blog
0%

資料結構-Binary Search Tree - insert method

發表於 更新於 分類於 ，
紀錄 Binary Search Tree 的 Insert 實作方法

insert 的程式碼如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
BST.prototype.insert = function(value) {
  if(value <= this.value) {
    if(!this.left) this.left = new BST(value);
    else this.left.insert(value);
  }
  else if(value > this.value) {
    if(!this.right) this.right = new BST(value);
    else this.right.insert(value);
  }
}

const bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(100);
bst.insert(60);
console.log(bst.right.left.value); // 60

解釋一下上面程式碼的內容

1
2
3
4
5
6
7
8
9
10
BST.prototype.insert = function(value) {
  if(value <= this.value) { // 是否新增的節點的值小於等於這個節點的值，若是，就要把這個節點設為此節點的左邊節點
    if(!this.left) this.left new Node(value); // 如果還沒有左邊節點，那就直接創一個新的，並將 left 指向這個新創的節點
    else this.left.insert(value); // 若已存在左邊節點，那就將要新增的值，傳給左邊節點 insert function
  }
  else if(value > this.value) { // 是否新增的節點的值大於這個節點的值，若是，就要把這個節點設為此節點的右邊節點
    if(!this.right) this.right = new BST(value);
    else this.right.insert(value);
  }
}

上面 insert 的過程就是下圖所示:
Imgur

遞迴的部分運用在呼叫 left 或 right 節點的 insert function。
而遞迴的終止條件有兩個:

  1. 當被遍歷到的 node 的 left node 為空，則新的 node 就會被加入在這個 left node 位置，遞迴終止。
  2. 當被遍歷到的 node 的 right node 為空，則新的 node 就會被加入在這個 right node 位置，遞迴終止。

Note:
若 left node 或者 right node 有存在的時候，
是要接續呼叫 left node 或 right node 的 insert function(i.e. this.left.insert(value)) 喔，不是呼叫當前被遍歷的 node 的 insert function，要小心不要寫錯了。

Conclusion

  • 遞迴這個功能是被用在呼叫節點的 insert function，以此一層一層的往下遍歷。