Binary Search Tree Contains#

找二元搜尋樹裡面的 node。

題目: 給一個值 x,請在 Binary Search Tree 內搜尋有無 x 並回傳該 node,若無則回傳 null。

想法#

前幾篇提到有兩種(Depth First, Breadth First)方式可以遍歷(Traversal)整個 Tree, 那在這題情況適合哪一種呢?

想想看,我們的 root node 下來左邊比它自己小,右邊比它自己大,所以只要找其中一邊就好, 那就是 Depth First 會比較適合。

與前一篇 Insert 差不多作法。

底下我們用 recursion 方式來解決此問題。

JavaScript 實作#

js

class Node {
constructor(data) {
this.data = data;
this.left = null;
this.right = null;
}
contains(data) {
// 若是 root 直接回傳 node
if(this.data === data){
return this;
}
if (this.data < data && this.right) {
return this.right.contains(data);
} else if (this.data > data && this.left) {
return this.left.contains(data);
}
// 上面條件都不符合,回傳 null
return null;
}

Java 實作#

Java

class BinarySearchTree {
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
Node root;
BinarySearchTree() {
root = null;
}
public Node contains(Node root, int key) {
if (root.key==key) {
return root;
}
if (root.key > key){
return contains(root.left, key);
} else if (root.key < key){
return contains(root.right, key);
}
return null
}
}

本文同時發布於鐵人賽