找二元搜尋樹裡面的 node。
題目: 給一個值 x,請在 Binary Search Tree 內搜尋有無 x 並回傳該 node,若無則回傳 null。
本文同時發布於好讀整理版
前幾篇提到有兩種(Depth First, Breadth First)方式可以遍歷(Traversal)整個 Tree,
那在這題情況適合哪一種呢?
想想看,我們的 root node 下來左邊比它自己小,右邊比它自己大,所以只要找其中一邊就好,
那就是 Depth First 會比較適合。
與前一篇 Insert 差不多作法。
底下我們用 recursion 方式來解決此問題。
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
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
}
}
今天的 找二元搜尋樹裡面的 node 就先到這邊,明天繼續有趣的題目...
敬請期待!!
本文同時發布於好讀整理版