[자료구조] Binary Search Tree(BST)

// BST.h

#include <iostream>

using namespace std;

#define Min_sort    0

#define Max_sort    1

template<typename T>

class BST;

template<typename T>

class node{

    private:

        T data;

        node<T> *left;

        node<T> *right;

    public:

        node() : left(NULL), right(NULL), data(0) { }

        friend class BST<T>;

};

template<typename nodetype>

class BST{

    private:

        node<nodetype> *root;

        node<nodetype> *P;      // Get Search Parent

    public:

        node<nodetype> *input(int input_d);

        node<nodetype> *Search(int input_d);

        node<nodetype> *GetLeftChild(node<nodetype> *Parent);

        node<nodetype> *GetRightChild(node<nodetype> *Parent);

        nodetype *LtoRPrint(node<nodetype> *Parent);

        nodetype *RtoLPrint(node<nodetype> *Parent);

        nodetype *Print(int sort_rule);

        bool del_node(int input_d);

        void input(nodetype input_arr[], int size);

};

template<typename nodetype>

node<nodetype> *BST<nodetype>::input(int input_d){

    if (root == NULL){

        root = new node<nodetype>;

        root->data = input_d;

        return root;

    }

    node<nodetype> *temp = Search(input_d);

    if(temp->data > input_d){

        temp->left = new node<nodetype>;

        temp = GetLeftChild(temp);

    }

    else if(temp->data < input_d){

       temp->right = new node<nodetype>;

        temp = GetRightChild(temp);

    }

    temp->data = input_d;

    return temp;

}

// Array Input~

template<typename nodetype>

void BST<nodetype>::input(nodetype input_arr[], int size){

    if (root == NULL){

        root = new node<nodetype>;

        root->data = input_arr[0];

    }

    int cnt;

    

    for(cnt=0; cnt < size; cnt++){

        node<nodetype> *temp = Search(input_arr[cnt]);

    

        if(temp->data > input_arr[cnt]){

            temp->left = new node<nodetype>;

            temp = GetLeftChild(temp);

        }

        else if(temp->data < input_arr[cnt]){

           temp->right = new node<nodetype>;

            temp = GetRightChild(temp);

        }

    

        temp->data = input_arr[cnt];

    }

}

template<typename nodetype>

bool BST<nodetype>::del_node(int input_d){

    node<nodetype> *del = Search(input_d);

    

    // Search 함수는 노드를 탐색하면서 같은값을 찾게 되었을때

    // 그 노드를 ret하지만, 없다면 최하위 노드를 ret하게 되므로 값을 비교해줘서

    // 분기를 해줘야한다.

    if(del->data != input_d)

        return false;

    

    // Case 1 : left, right NULL

    if(GetLeftChild(del) == NULL && GetRightChild(del) == NULL){

        if(P->left != NULL)

            if(P->left->data == del->data)

                P->left = NULL;

        if(P->right != NULL)

            if(P->right->data == del->data)

                P->right = NULL;

        delete del;

        

        if(del == root)

            root = NULL;

    }

    // Case 2 : left and right not NULL

    else if(GetLeftChild(del) != NULL && GetRightChild(del) != NULL){

        node<nodetype> *temp = del;

        node<nodetype> *p_temp = del;

        

        temp = GetRightChild(del);

        while(GetLeftChild(temp) != NULL){

            p_temp = temp;

            temp = GetLeftChild(temp);

        }

        if(P->left == del){

            temp->left = del->left;

            P->left = temp;

        }

        else if(P->right == del){

            temp->left = del->left;

            P->right = temp;

        }

        else if(P == del){

            //P->data = temp->data;

            P->right = temp->right;

        }

        delete del;

    }

    // Case 3 : have one Child

    else{

        if(P->left == del){

            if(GetLeftChild(del) != NULL)

                P->left = GetLeftChild(del);

            else

                P->left = GetRightChild(del);

        }

        else if(P->right == del)

            if(GetLeftChild(del) != NULL)

                P->right = GetLeftChild(del);

            else

                P->right = GetRightChild(del);

        delete del;

    }

    return true;

}

template<typename nodetype>

node<nodetype> *BST<nodetype>::Search(int input_d){

    node<nodetype> *temp = root;

    P = root;

    while(temp->left != NULL || temp->right != NULL){

        if(temp->data > input_d && GetLeftChild(temp) != NULL){

            P = temp;

            temp = GetLeftChild(temp);

        }

        else if(temp->data < input_d && GetRightChild(temp) != NULL){

            P = temp;

            temp = GetRightChild(temp);

        }

        else

            break;

    }

    return temp;

}

template<typename nodetype>

node<nodetype> *BST<nodetype>::GetLeftChild(node<nodetype> *Parent){

    return Parent->left;

}

template<typename nodetype>

node<nodetype> *BST<nodetype>::GetRightChild(node<nodetype> *Parent){

    return Parent->right;

}

template<typename nodetype>

nodetype *BST<nodetype>::Print(int sort_rule){

    if(sort_rule == Min_sort)

        return LtoRPrint(root);

    else if(sort_rule == Max_sort)

        return RtoLPrint(root);

}

template<typename nodetype>

nodetype *BST<nodetype>::LtoRPrint(node<nodetype> *Parent){

    if(Parent == NULL)

        return NULL;

    LtoRPrint(Parent->left);

    cout << Parent->data << endl;

    LtoRPrint(Parent->right);

}

template<typename nodetype>

nodetype *BST<nodetype>::RtoLPrint(node<nodetype> *Parent){

    if(Parent == NULL)

        return NULL;

    RtoLPrint(Parent->right);

    cout << Parent->data << endl;

    RtoLPrint(Parent->left);

}

//BST.cpp

#include <iostream>

#include <cstdlib>

#include "BST.h"

using namespace std;

int main()

{

    BST<int> *bst = new BST<int>;

    int arr[1000], i;

    

    srand(time(NULL));

    for(i = 0; i < 1000; i++)

        arr[i] = rand() % 10000 + 1;

    

    bst->input(arr,1000);

    bst->Print(Min_sort);

    delete bst;

    return 0;

}