今日目標：

1. BST::getMax()
2. BST::getMin()
3. BST::search(int tg) (註：tg 為 target 的縮寫)

定義類別

class BST {
private:
    BSTNode *root;
public:
    BST();
    // insert methods
    // traversal methods
    BSTNode *getMax();
    BSTNode *getMax(BSTNode *);
    BSTNode *getMin();
    BSTNode *getMin(BSTNode *);
    BSTNode *search(int);
    BSTNode *search(BSTNode *, int);
};

為什麼每一個類別方法都要有兩種型態（有/無參數）？
因為有的時候，我們的根節點可能是子樹的根節點，這時候我們就要給定參數。

BST::getMax()

哪一個節點會是二元搜尋樹的最大值呢？
我們先想想怎麼實作 BST::insert()，當數值比根節點的數值還大，就向右邊走！
因此樹的最最最右邊的那個節點就是我們的答案。

BSTNode *BST::getMax() {
    if (this -> root == NULL) return NULL;
    BSTNode *cur = this -> root;
    while (cur -> right) cur = cur -> right;
    return cur;
}

BSTNode *BST::getMax(BSTNode *root) {
    if (root == NULL) return NULL;
    BSTNode *cur = root;
    while (cur -> right) cur = cur -> right;
    return cur;
}

BST::getMin()

哪一個節點會是二元搜尋樹的最小值呢？
我們先想想怎麼實作 BST::insert()，當數值比根節點的數值還小，就向左邊走！
因此樹的最最最左邊的那個節點就是我們的答案。

BSTNode *BST::getMin() {
    if (this -> root == NULL) return NULL;
    BSTNode *cur = this -> root;
    while (cur -> left) cur = cur -> left;
    return cur;
}

BSTNode *BST::getMin(BSTNode *root) {
    if (root == NULL) return NULL;
    BSTNode *cur = root;
    while (cur -> left) cur = cur -> left;
    return cur;
}

BST::search()

根據二元搜尋樹的規則，數值較大，就往右走，數值較小，就往左走！

直到沒有路可以走。

BSTNode *BST::search(int tg) {
    if (this -> root == NULL) {
        return NULL;
    }
    BSTNode *cur = this -> root;
    while (cur) {
        if (cur -> data == tg) {
            return cur;
        }
        else if (cur -> data > tg) { // go left
            if (cur -> left) {
                cur = cur -> left;
            }
            else {
                return NULL;
            }
        }
        else {
            if (cur -> right) {
                cur = cur -> right;
            }
            else {
                return NULL;
            }
        }
    }
    return NULL;
    
}

BSTNode *BST::search(BSTNode *root, int tg) {
    if (root == NULL) {
        return NULL;
    }
    BSTNode *cur = root;
    while (cur) {
        if (cur -> data == tg) {
            return cur;
        }
        else if (cur -> data > tg) { // go left
            if (cur -> left) {
                cur = cur -> left;
            }
            else {
                return NULL;
            }
        }
        else {
            if (cur -> right) {
                cur = cur -> right;
            }
            else {
                return NULL;
            }
        }
    }
    return NULL;
    
}

下一篇，我們要介紹最難的類別方法：BST::remove()