今天我們要完成以下的狀況：

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

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

定義 BST::remove()

BSTNode *BST::remove(int target) {
    BSTNode *tg = search(target);
    // 目標節點不存在或二元搜尋樹為空
    if (tg == NULL) {
        std::cout << "NOT FOUND" << std::endl;
        return NULL;
    }
    // 目標節點為樹根
    if (tg == this -> root) { // remove root
        if (tg -> left && tg -> right) { // 2 children
            // tg will be replaced by min of tg -> right
            BSTNode *replaced = getMinPtr(tg -> right);
            if (replaced -> right) {
                if (replaced -> parent -> right == replaced) {
                    replaced -> parent -> right = replaced -> right;
                }
                else {
                    replaced -> parent -> left = replaced -> right;
                }
            }
            if (tg -> right == replaced) {
                replaced -> left = tg -> left;
                tg -> left -> parent = replaced;
            }
            else {
                replaced -> right = tg -> right;
                replaced -> left = tg -> left;
                tg -> right -> parent = replaced -> right;
                tg -> left -> parent = replaced -> left;
            }
            this -> root = replaced;
            return tg;

        }
        else if (tg -> left) { // 1 child : left
            this -> root = tg -> left;
            return tg;
        }
        else if (tg -> right) { // 1 child : right
            this -> root = tg -> right;
            return tg;
        }
        else { // no child
            this -> root = NULL;
            return tg;
        }
    }
    // 目標節點存在，但不為樹根
    else {
        if (tg -> left && tg -> right) { // 2 children
            // tg will be replaced by min of tg -> right
            BSTNode *replaced = getMinPtr(tg -> right);
            if (replaced -> right) {
                if (replaced -> parent -> right == replaced) {
                    replaced -> parent -> right = replaced -> right;
                }
                else {
                    replaced -> parent -> left = replaced -> right;
                }
            }
            replaced -> parent = tg -> parent;
            if (tg -> parent -> right == tg) {
                tg -> parent -> right = replaced;
            }
            else {
                tg -> parent -> left = replaced;
            }
            replaced -> right = tg -> right;
            replaced -> left = tg -> left;
            tg -> right -> parent = replaced -> right;
            tg -> left -> parent = replaced -> left;
            return tg;
        }
        else if (tg -> left) { // 1 child : left
            concat(&(tg -> parent), &tg, &(tg -> left));
            return tg;
        }
        else if (tg -> right) { // 1 child : right
            concat(&(tg -> parent), &tg, &(tg -> right));
            return tg;
        }
        else { // no child
            if (tg -> parent -> left == tg) {
                tg -> parent -> left = NULL;
            }
            else {
                tg -> parent -> right = NULL;
            }
            return tg;
        }

    }

}

// 用來銜接目標節點的父節點與子節點
void concat(Node **tgp, Node **tg, Node **tgc) { 
    if ((*tgp) -> left == *tg) {
        (*tgc) -> parent = (*tgp);
        (*tgp) -> left = (*tgc);
        return ;
    }
    else {
        (*tgc) -> parent = (*tgp);
        (*tgp) -> right = (*tgc);
        return ;
    }
}

二元搜尋樹就介紹到這裡，接下來我們來試試看相關的題目吧！