contains 在幹嘛?
contains 這個方法專門是來搜尋 tree 裡面是否有想要搜尋的搜尋值。
contains 的實作程式碼?
其實作的程式碼如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| BST.prototype.contains = function(value) {
if(this.value === value) return true;
if(value < this.value) {
if(!this.left) return false;
else return this.left.contains(value);
}
else {
if(!this.right) return false;
else return this.right.contains(value);
}
}
const bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(100);
bst.insert(60);
bst.insert(30);
bst.insert(59);
bst.insert(20);
bst.insert(45);
bst.insert(35);
bst.insert(85);
bst.insert(105);
bst.insert(10);
console.log(bst.right && bst.right.right); // 100
console.log(bst.contains(1000)) // false
|
解析一下 contains method 裡面的程式碼各是什麼意思
1
| if(this.value === value) return true; // 如果當前 node 的值等於搜尋值的話，就回傳 true，代表找到了。
|
1
2
3
4
5
6
7
8
| if(value < this.value) { // 如果搜尋值小於當前 node 的值
if(!this.left) return false; // 若左邊的子 node 不存在，代表此 node 已經是 tree 的最末端，代表已經遍尋的整個 tree 了，但還是沒找到，所以，回傳 false
else return this.left.contains(value); // 若左邊的子 node 存在，代表還沒遍歷整個 tree，那就把搜尋值丟到左邊子 node 的 contains 方法，繼續往下搜尋
}
else { // 如果搜尋值大於當前 node 的值
if(!this.right) return false; // 若右邊的子 node 不存在，代表此此 node 已經是 tree 的最末端，代表已經遍歷了整個 tree 但還是找不到，所以，回傳 false
else return this.right.contains(value); // 若右邊的子 node 存在，代表還沒完成遍歷整個 tree，那就把搜尋值丟到右邊子 node 的 contains 方法，繼續往下搜尋
}
|
Conclusion
- 知道如何製作 binary search tree 的搜尋方法
Reference Link