Landy Blog
0%

資料結構-Binary Search Tree - 整體結構

發表於 更新於 分類於 ，
紀錄 Binary Search Tree 的是由什麼構成的，與 tree 裡的 node 有什麼屬性，並且要怎麼實作 node

Binary Search Trees 的結構

在 tree 裡面的每一個 root node 都可以包含至多兩個子 node。
在 root node 左手邊的 node 所帶的值，都會小於或等於 root node 帶的值。
在 root node 右手邊的 node 所帶的值，都會大於 root node 帶的值。
Imgur

Note:
上面講每一個 root node 可以包含至多兩個子 node，會特別說明至多是因為，root node 也有可能只包含一個子 node。

Binary Search Tree 的結構圖如下:
Imgur
上面這個 binary search tree 拆細一點來看的話，可以看出來它也是由多個小 tree 所組成，
即: 由 [4,2,6], [2,1,3], [6,5,7] 這三個小的 binary search tree 組成以上這個大的 binary search tree。

每一個 node 含有的成員屬性

以下是每一個 node 都會含有的成員屬性
Imgur

分別為:
value: 此 node 所帶的值
left: 此 node 的左邊的子 node 的參照
right: 此 node 的右邊的子 node 的參照

以下是 node 的實作程式碼:

1
2
3
4
5
6
7
function BST(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

const bst = new BST(50);

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

1
2
3
4
5
6
7
8
9
10
11
/*
  這是 node 的建構式，
  value 就是將外部傳進來的 value 參數的值設給它，
  left 就是指向左邊子節點的指標，但是，新節點還不會有左邊節點，所以，初始值為 null，
  right 就是指向右邊子節點的指標，但是，新節點還不會有右邊節點，所以，初始值為 null，
*/
function BST(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}

Conclusion

  • Binary Search Tree 是由多個 node 所組成的。
  • node 擁有 value, left, right 這三個成員屬性。
  • node 的左節點的值會小於等於 parent node，右節點大於 parent node。