Untitled

#include <iostream>
#include <string>
using namespace std;

template <class T> class bst;

template <class T> class btNode{
    friend class bst<T>;
    public:
    btNode(): lchild(0),rchild(0),parent(0) {};
    btNode(T x): key(x),lchild(0),rchild(0),parent(0) {};
    private:
    T key;
    btNode<T> *lchild,*rchild,*parent;
};

template <class T> class bst{
    public:
    bst(): root(0) {};
    void trave(btNode<T> *p);
    void traverse();
    void insert(T x);
    void DeleteBST(T KEY);
    btNode<T>* search(T x);
    private:
    btNode<T> *root;
    btNode<T>* leftmost(btNode<T> *p);
    btNode<T>* Successor(btNode<T> *current);
    btNode<T>* rightmost(btNode<T> *p);
    btNode<T>* Predecessor(btNode<T> *current);
};

template <class T> btNode<T>* bst<T>::leftmost(btNode<T>* p){
    while(p->lchild) p=p->lchild;
    return p;
}

template <class T> btNode<T>* bst<T>::Successor(btNode<T> *current){
    
    if (current->rchild != NULL){
        return leftmost(current->rchild);
    }
    
    btNode<T> *new_node = current->parent;
    
    while (new_node != NULL && current == new_node->rchild) {
        current = new_node;
        new_node = new_node->parent;
    }
    
    return new_node;
}

template <class T> btNode<T>* bst<T>::rightmost(btNode<T> *p){
    while(p->rchild) p=p->rchild;
    return p;
}

template <class T> btNode<T>* bst<T>::Predecessor(btNode<T> *current){
    if (current->lchild != NULL){
        return rightmost(current->lchild);
    }

    btNode<T> *new_node = current->parent;

    while (new_node != NULL && current == new_node->lchild) {
        current = new_node;
        new_node = new_node->parent;
    }
    return new_node;
}

template <class T> void bst<T>::insert(T x){
    btNode<T> *p=new btNode<T>(x);
    if(!root) this->root=p;
    else {
        btNode<T> *q,*r;
        q=root;
        while(q){
            r=q;
            if(p->key < q->key) q=q->lchild;
            else q=q->rchild;   
        }
        //now r become parent of insert node
        p->parent=r;
        //insert p to its parent
        if (p->key < r->key) {r->lchild=p;}
        else r->rchild=p;
    }
}

template <class T> btNode<T>* bst<T>::search(T x){
    btNode<T> *p;
    while(p){
        if(x == p->key) break;
        else if (x < p->key) p=p->lchild;
        else p=p->rchild;
    }
    return p;
}

template <class T> void bst<T>::DeleteBST(T KEY){               // 要刪除具有KEY的node

    btNode<T> *delete_node = search(KEY);    // 先確認BST中是否有具有KEY的node
    if (delete_node == NULL) return;
    
    btNode<T> *y = 0;      // 真正要被刪除並釋放記憶體的node
    btNode<T> *x = 0;      // 要被刪除的node的"child"

    if (delete_node->lchild == NULL || delete_node->rchild == NULL){
        y = delete_node;
    }
    else{
        y = Successor(delete_node);        // 將y設成delete_node的Successor                          
    }                                      // 經過這組if-else, y調整成至多只有一個child
                                           // 全部調整成case1或case2來處理
    if (y->lchild != NULL){              
        x = y->lchild;                  // 將x設成y的child, 可能是有效記憶體,
    }                                      // 也有可能是NULL
    else{
        x = y->rchild;
    }
    
    if (x != NULL){                        // 在y被刪除之前, 這個步驟把x接回BST 
        x->parent = y->parent;             // 此即為圖二(c)中, 把基紐接回龜仙人的步驟
    }
                                           // 接著再把要被釋放記憶體的node之"parent"指向新的child
    if (y->parent == NULL){                // 若刪除的是原先的root, 就把x當成新的root 
        this->root = x;
    }
    else if (y == y->parent->lchild){    // 若y原本是其parent之left child
        y->parent->lchild = x;           // 便把x皆在y的parent的left child, 取代y
    }
    else{                                   // 若y原本是其parent之right child
        y->parent->rchild = x;          // 便把x皆在y的parent的right child, 取代y
    }                                       
                                            // 針對case3
    if (y != delete_node) {                 // 若y是delete_node的替身, 最後要再將y的資料
        delete_node->key = y->key;          // 放回delete_node的記憶體位置, 並將y的記憶體位置釋放
  // 圖二(d), y即是達爾, delete_node即是西魯
    }

    delete y;                               // 將y的記憶體位置釋放
    y = 0;
}

template <class T> void bst<T>::trave(btNode<T> *p){
    cout << p->key << ' ';
    if(p->lchild) trave(p->lchild);
    if(p->rchild) trave(p->rchild);
}

template <class T> void bst<T>::traverse(){
    if(!root) return;
    trave(root);
    cout << endl;
}

int main(){
    bst<int> bt;
    string cmd;
    while(cin >> cmd && !cin.eof()){
        if(cmd == "Traverse") bt.traverse();
        else if (cmd == "Insert") {int x; cin >> x; bt.insert(x);}
        else if (cmd == "Delete") {int x; cin >> x; bt.DeleteBST(x);}
    }
}