刪除節點一向都是比較困難的，我們要去注意

1. 根節點是不是我們要去刪除的目標節點
2. 如何連接目標節點的父節點與子節點
3. 如果目標節點有兩個子節點，又該如何與父節點連接呢？

諸多問題我們就來一一解決吧！

定義類別

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

尋找目標節點

尋找目標節點的方式很簡單，只要使用之前做過的函式 BSTNode *BST::search(int target) ，即可取得目標節點！

目標節點（BSTNode *tg）可以分成三種狀況：

1. tg == NULL : 目標不存在
2. tg == this -> root : 目標為樹根
   1. 目標無子節點：刪除後樹為空樹
   2. 目標有一個子節點：根改為該子節點
   3. 目標有兩個子節點：「註一」
3. else : 目標不為樹根
   1. 目標無子節點：直接刪除該目標
   2. 目標有一個子節點：對接目標節點的父節點與子節點
   3. 目標有兩個子節點：「註二」

註一、二

先想想目標節點有什麼特性？
這個節點的數值較左子樹的任一節點數值大，且較右子樹的任一節點數值小。

因此如果要找一個節點來頂替目標節點的位置，他也必須要有這個屬性，而這個特性的節點有兩個：

1. 左子樹的最大者
2. 右子樹的最小者

這兩個節點有什麼特性？
至少有一邊為 NULL
有了這個特性，我們可以更輕鬆的將該節點轉移為頂替目標節點的節點。

註一與註二最大的不同是，我們是否有機會改到根節點！

下一篇，我們正式進入程式碼的部分。