이진 탐색 트리(Binary Search Tree)

이진 탐색 트리란, 다음과 같은 특징을 갖는 이진 트리이다

• 모든 노드의 값은 유일하다.

• 왼쪽 노드의 값은 자신의 값보다 작다.

• 오른쪽 노드의 값은 자신의 값보다 크다.

• 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

---

이진 탐색 트리 클래스를 Node 구조체를 사용한 링크 표현법으로 구현하였다.

모든 함수들은 재귀로 구현하였다.

#include <iostream>
#include <algorithm>

using namespace std;

struct Node
{
    int data;
    Node* left;
    Node* right;
};

class BinaryTree
{
public:
    BinaryTree();
    ~BinaryTree();
    int size();
    int height();
    bool search(int key);
    bool insert(int item);
    bool remove(int key);
    void print();
private:
    Node* root;
};
BinaryTree::BinaryTree()
{
    root = NULL;
}
void recur_remove(Node* tree)
{
    if(tree != NULL)
    {
        recur_remove(tree->left);
        recur_remove(tree->right);
        delete tree;
    }
}
BinaryTree::~BinaryTree()
{
    recur_remove(root);
}
int recur_size(Node* tree)
{
    if(tree == NULL) return 0;
    else return recur_size(tree->left) + recur_size(tree->right) + 1;
}
int BinaryTree::size()
{
    return recur_size(root);
}
int recur_height(Node* tree)
{
    if(tree == NULL) return 0;
    else return max(recur_height(tree->left), recur_height(tree->right)) + 1;
}
int BinaryTree::height()
{
    recur_height(root);
}
bool recur_search(Node* tree, int key)
{
    if(tree == NULL) return false;

    if(tree->data == key) return true;
    else if(tree->data > key) return recur_search(tree->left, key);
    else return recur_search(tree->right, key);
}
bool BinaryTree::search(int key)
{
    return recur_search(root, key);
}
bool recur_insert(Node* &tree, int item)
{
    if(tree == NULL)
    {
        tree = new Node;
        tree->data = item;
        tree->left = NULL;
        tree->right = NULL;
        return true;
    }
    if(tree->data == item) return false;
    else if(tree->data > item) return recur_insert(tree->left, item);
    else return recur_insert(tree->right, item);
}
bool BinaryTree::insert(int item)
{
    return recur_insert(root, item);
}
bool recur_remove(Node* &tree, int key)
{
    if(tree == NULL) return false;

    if(tree->data > key) return recur_remove(tree->left, key);
    else if(tree->data < key) return recur_remove(tree->right, key);
    else
    {
        Node* tmp;
        if(tree->left == NULL)
        {
            tmp = tree;
            tree = tree->right;
            delete tmp;
            return true;
        }
        else if(tree->right == NULL)
        {
            tmp = tree;
            tree = tree->left;
            delete tmp;
            return true;
        }
        else
        {
            tmp = tree->right;
            while(tmp->left != NULL)
            {
                tmp = tmp->left;
            }
            tree->data = tmp->data;
            recur_remove(tree->right, tmp->data);
            return true;
        }
        return false;
    }
}
bool BinaryTree::remove(int key)
{
    recur_remove(root, key);
}
void recur_print(Node* tree)
{
    if(tree != NULL)
    {
        recur_print(tree->left);
        cout<<"<"<<tree->data<<"> ";
        recur_print(tree->right);
    }
}
void BinaryTree::print()
{
    recur_print(root);
    cout<<endl;
}

int main()
{
    BinaryTree bt;

    bt.insert(1);
    bt.insert(2);
    bt.insert(3);
    bt.print();

    if(bt.search(3)) cout<<"find 3!!"<<endl;
    else cout<<"3 not found"<<endl;

    bt.remove(2);
    bt.print();

    if(bt.search(2)) cout<<"find 2!!"<<endl;
    else cout<<"2 not found"<<endl;
    return 0;
}