BinarySearchingTree_ClassVersion

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


class binary_tree_node
{
    friend class BST;
    public:
        binary_tree_node(int data):left(NULL),right(NULL)
        {
            _data = data;
        }
        ~binary_tree_node(){
        }
        int _data;
        binary_tree_node *left;
        binary_tree_node *right;

};
typedef class binary_tree_node node;


class BST{
    public:
        void insert_node(int value){
            insert_nodeHelper(value);
        }
        void print_InOrder(){
            print_InOrderHelper(root);
        }
        void print_PreOrder(){
            print_PreOrderHelper(root);
        }
        void print_PostOrder(){
            print_PostOrderHelper(root);
        }
        void search_node(int value){
            if (search_nodeHelper(value))
                cout << "found: " << value << endl;
            else
                cout << "not found" << endl;
        }
        void delete_node(int value){
            if (delete_nodeHelper(value))
                cout << "delete ok" << endl;
            else
                cout << "delete failed" << endl;
        }

    private:
        node* root;
        void insert_nodeHelper(int value);
        void print_InOrderHelper(node* ptr);
        void print_PreOrderHelper(node* ptr);
        void print_PostOrderHelper(node* ptr);
        node* search_nodeHelper(int value);
        bool delete_nodeHelper(int value);

};


int main(){

    BST myBST;
    int value;
    while(1){
        cout << "i insert"
             << "\nl list"
             << "\nf find"
             << "\nd delete"
             << "\nq quit"<< endl;

        char sel;
        cin >> sel;
        switch(sel){
            case 'i':
                cout << "please input the value for the new node: ";
                cin >> value;
                myBST.insert_node(value);
                break;

            case 'l':
                cout << "PreOrder Traversal: ";
                myBST.print_PreOrder();
                cout << "\nInOrder Traversal: ";
                myBST.print_InOrder();
                cout << "\nPostOrder Traversal: ";
                myBST.print_PostOrder();
                break;

            case 'f':
                cout << "please input the value for the new node: ";
                cin >> value;
                myBST.search_node(value);
                break;

            case 'd':
                cout << "please input the value: ";
                int value;
                cin >> value;
                myBST.delete_node(value);
                break;

            case 'q':
                exit(0);
        }

        system("pause");
        system("cls");
    }


//  delete root;
}



void BST::insert_nodeHelper(int value){
    node *current;
    node *parent;

    if (root != NULL){
        current = root;
        while (current != NULL){
            parent = current;

            if (current->_data > value)
                current = current->left;
            else if (current->_data < value)
                current = current->right;
            else{
                cout << "duplucate value" << endl;
                return;
            }
        }
        // now, we've got the parent node from which
          //  we are gonna insert our new node underneath

        if (parent->_data > value)
            parent->left = new node(value);
        else if (parent->_data < value)
            parent->right = new node(value);
    }else{
        root = new node(value);
    }
}

void BST::print_InOrderHelper(node* ptr){
    if (ptr == NULL)
        return;
    print_InOrderHelper(ptr->left);
    cout << ptr->_data << " "; // key command
    print_InOrderHelper(ptr->right);
}
void BST::print_PreOrderHelper(node* ptr){
    if (ptr == NULL)
        return;
    cout << ptr->_data << " "; // key command
    print_PreOrderHelper(ptr->left);
    print_PreOrderHelper(ptr->right);
}
void BST::print_PostOrderHelper(node* ptr){
    if (ptr == NULL)
        return;
    print_PostOrderHelper(ptr->left);
    print_PostOrderHelper(ptr->right);
    cout << ptr->_data << " "; // key command
}
node* BST::search_nodeHelper(int value){
    node* ptr = root;

    while (ptr != NULL){
        if (ptr->_data == value)// 若第一個就中，那要找的就是根節點
            return ptr;

        ptr = (ptr->_data > value)? ptr->left : ptr->right;
    }// end while

    return NULL;
}

bool BST::delete_nodeHelper(int value){
    node* itemDeleted;
    node* parent = NULL;
    node* ptr = root;

    while (ptr != NULL){
        if (ptr->_data == value){ // 若第一個就中，那要刪的就是根節點
            itemDeleted = ptr;
            break;
        }
        parent = ptr;
        ptr = (ptr->_data > value)? ptr->left : ptr->right;
    }// end while

    if (ptr == NULL) {
        cout << value << " doesn't exist. "<< endl;
        return false;
    };

    // 要刪的節點沒有左子樹
    if (itemDeleted->left == NULL){
        // 要刪的節點是根節點
        if (itemDeleted == root){
            root = root->right;
        // 要刪的節點在其父節點左方
        }else if (itemDeleted == parent->left){
            parent->left = itemDeleted->right;
        // 要刪的節點在其父節點右方
        }else if (itemDeleted == parent->right){
            parent->right = itemDeleted->right;
        }
        delete itemDeleted;
    // 要刪的節點沒有右子樹
    }else if(itemDeleted->right == NULL){
        // 要刪的節點是根節點
        if (itemDeleted == root){
            root = root->left;
        // 要刪的節點在其父節點左方
        }else if (itemDeleted == parent->left){
            parent->left = itemDeleted->left;
        // 要刪的節點在其父節點右方
        }else if (itemDeleted == parent->right){
            parent->right = itemDeleted->left;
        }
        delete itemDeleted;
    // 要刪的節點有左右子樹
    }else{
        // 從左子樹中找出最大的節點(小於且最接近要被刪除的節點值)
        node* subparent = itemDeleted;
        node* closestNo = itemDeleted->left;

        if (closestNo->right != NULL){
            while(closestNo->right != NULL){
                subparent = closestNo;
                closestNo = closestNo->right;
            }
            subparent->right = closestNo->left;
            itemDeleted->_data = closestNo->_data;
        // 特殊狀況：本要來刪的節點左子節點值就是最大的數了
        }else{
            subparent->left = closestNo->left;
            itemDeleted->_data = closestNo->_data;
        }
        // 注意：這裡要刪的，是跟原本要刪的節點對掉的那個節點
        delete closestNo;
    }
    return true;
}