[C++/템플릿으로 만드는 자료구조] 이진탐색트리(Binary Search Tree)

C++/템플릿으로 만든 이진탐색 트리 소스입니다. iostream을 인클루드해야 사용할 수 있습니다.

enum { _Inorder, _Preorder, _Postorder };
 
template<typename Type>
class TreeNode
{
public:
    Type key;
    TreeNode<Type> *LNode;
    TreeNode<Type> *RNode;
};
 
template<typename Type>
class Tree
{
private:
    TreeNode<Type> *Root;
 
public:
    Tree();
    ~Tree();
    bool Is_There(Type Item);
    void Add(Type Item);
    Type Delete(Type Item);
    void Inorder(TreeNode<Type> *Target_Tree);
    void Preorder(TreeNode<Type> *Target_tree);
    void Postorder(TreeNode<Type> *Target_Tree);
    void Printing(int select);
};
 
template<typename Type>
Tree<Type>::Tree()
{
    this->Root = NULL;
}
 
template<typename Type>
Tree<Type>::~Tree()
{
 
}
 
template<typename Type>
bool Tree<Type>::Is_There(Type Item)
{
    TreeNode<Type> *Cur = this->Root;
    while (1)
    {
        if (Cur->key == Item)
        {
            return true;
        }
        if (Cur->key < Item)
        {
            if (Cur->RNode == NULL)
                return false;
            Cur = Cur->RNode;
        }
        else
        {
            if (Cur->LNode == NULL)
                return false;
            Cur = Cur->LNode;
        }
    }
}
 
template<typename Type>
void Tree<Type>::Add(Type Item)
{
    TreeNode<Type> *NewNode = new TreeNode<Type>;
    if (this->Root == NULL)
    {
        this->Root = NewNode;
        NewNode->LNode = NULL;
        NewNode->RNode = NULL;
        NewNode->key = Item;
        return;
    }
    if (this->Is_There(Item))
    {
        std::cout << "Already Exist" << std::endl;
        return;
    }
    NewNode->LNode = NULL;
    NewNode->RNode = NULL;
    NewNode->key = Item;
    TreeNode<Type> *Cur = this->Root;
    while (1)
    {
        if (Cur->key < Item)
        {
            if (Cur->RNode == NULL)
            {
                Cur->RNode = NewNode;
                return;
            }
            Cur = Cur->RNode;
        }
        else
        {
            if (Cur->LNode == NULL)
            {
                Cur->LNode = NewNode;
                return;
            }
            Cur = Cur->LNode;
        }
    }
}
 
template<typename Type>
Type Tree<Type>::Delete(Type Item)
{
    TreeNode<Type> *Cur2 = NULL;
    TreeNode<Type> *Cur = this->Root;
    TreeNode<Type> *Par_Parent = NULL;
    TreeNode<Type> *Parent = NULL;
    TreeNode<Type> *Child = NULL;
    TreeNode<Type> *Left_Temp = NULL;
    int Key_return = 0;
    if (!(this->Is_There(Item)))
    {
        std::cout << "There is no that Value\n" << std::endl;
        return 0;
    }
    while (Cur->key != Item)
    {
        if (Item > Cur->key)
        {
            Par_Parent = Parent;
            Parent = Cur;
            Cur = Cur->RNode;
        }
        else
        {
            Par_Parent = Parent;
            Parent = Cur;
            Cur = Cur->LNode;
        }
    }//특정 값 까지 이동
    if (Cur->LNode == NULL&&Cur->RNode == NULL)//터미널 노드일 때
    {
        Key_return = Cur->key;
        if (Parent->LNode == Cur)
            Parent->LNode = NULL;
        if (Parent->RNode == Cur)
            Parent->RNode = NULL;
        delete(Cur);
        return Key_return;
    }
 
    if (Cur->LNode == NULL || Cur->RNode == NULL)//지우려는 값 아래에 1개의 자식이 있을 때
    {
        Child = (Cur->LNode != NULL) ? Cur->LNode : Cur->RNode;
 
        if (Parent->LNode == Cur)//지우려는 값의 부모 의 어느자식이 지우려는 값인지?
            Parent->LNode = Child;
        else
            Parent->RNode = Child;
        Key_return = Cur->key;
        delete(Cur);
        return Key_return;
    }
 
    if (Cur->LNode != NULL&&Cur->RNode != NULL)//지우려는 값 아래에 2개 자식이 있을 때
    {
        Cur2 = Cur;
        Cur2 = Cur2->RNode;
        if (Cur2->LNode == NULL)//오른쪽 한칸 이동 후 왼쪽에 노드가 없을 때 
        {
            Left_Temp = Cur->LNode;
            Child = Cur2;
            if (Parent->RNode == Cur)
            {
                Parent->RNode = Child;
                Child->LNode = Left_Temp;
            }
            else
                if (Parent->LNode == Cur)
                {
                    Parent->LNode = Child;
                    Child->LNode = Left_Temp;
                }
            Key_return = Cur->key;
            delete(Cur);
            return Key_return;
        }
        while (Cur2->LNode != NULL)//오른쪽 한칸 이동후 왼쪽에 노드가 있을 때
        {
            Parent = Cur2;
            Cur2 = Cur2->LNode;
        }
        Parent->LNode = NULL;
        Cur->key = Cur2->key;
        delete(Cur2);
    }
    return 0;
}
 
template<typename Type>
void Tree<Type>::Printing(int select)
{
    switch (select)
    {
 
    case _Inorder:
        this->Inorder(this->Root);
        std::cout << std::endl;
        break;
 
    case _Preorder:
        this->Preorder(this->Root);
        std::cout << std::endl;
        break;
 
    case _Postorder:
        this->Postorder(this->Root);
        std::cout << std::endl;
        break;
 
    default:
        break;
    }
}
 
template<typename Type>
void Tree<Type>::Inorder(TreeNode<Type> *Target_Tree)
{
    if (Target_Tree == NULL)
        return;
    this->Inorder(Target_Tree->LNode);
    std::cout << Target_Tree->key << " ";
    this->Inorder(Target_Tree->RNode);
}
 
template<typename Type>
void Tree<Type>::Preorder(TreeNode<Type> *Target_Tree)
{
    if (Target_Tree == NULL)
        return;
    std::cout << Target_Tree->key << " ";
    this->Preorder(Target_Tree->LNode);
    this->Preorder(Target_Tree->RNode);
}
 
template<typename Type>
void Tree<Type>::Postorder(TreeNode<Type> *Target_Tree)
{
    if (Target_Tree == NULL)
        return;
    this->Postorder(Target_Tree->LNode);
    this->Postorder(Target_Tree->RNode);
    std::cout << Target_Tree->key << " ";
}

이진탐색트리는 이후 STL에서 set, map 등을 이용할 때 사용하게됩니다.

같이보기

2015/12/16 - [Programming/자료구조] - [C로 만드는 자료구조]트리(Tree)

2015/12/17 - [Programming/자료구조] - [C로 만드는 자료구조]이진 트리(Binary Tree) - 배열

2015/12/18 - [Programming/자료구조] - [C로 만드는 자료구조]이진 트리(Binary Tree) - 순회