[알고리즘/자료구조] 이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리

컴퓨터 과학에서 이진 탐색 트리(BST: binary search tree)는 다음과 같은 속성이 있는 이진 트리 자료 구조이다.

각 노드에 값이 있다.

값들은 전순서가 있다.

노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.

노드의 오른쪽 서브트리에는 그 노드의 값과 같거나 큰 값들을 지닌 노드들로 이루어져 있다.

좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.

소스

/*
/*
/*    khsh5592@naver.com
/*    has3ong.tistory.com
/*
/*    2018 - 11 - 29
/*
*/
 
#include <stdio.h>
#include <iostream>
#include <conio.h>
 
using namespace std;
 
 
class TreeNode
{
public:
    TreeNode* Left_Child;
    TreeNode* Right_Child;
 
    int Data;
 
    TreeNode* create_Node(int newData);
    void add_Node(TreeNode* Tree, TreeNode *Node);
    TreeNode* search_Node(TreeNode* Tree);
    TreeNode* search_Node(TreeNode* Tree, int data);
    TreeNode* remove_Node(TreeNode* Tree, TreeNode* Parent, int data);
    void PreorderPrint(TreeNode* Node);
    void InorderPrint(TreeNode* Node);
    void PostorderPrint(TreeNode* Node);
};
 
TreeNode* create_Node(int newData)
{
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode) );
    newNode->Left_Child = NULL;
    newNode->Right_Child = NULL;
    newNode->Data = newData;
 
    return newNode;
}
 
void add_Node(TreeNode* Tree, TreeNode *Node)
{
    if (Tree -> Data < Node -> Data)
    {
        if (Tree->Right_Child == NULL)
        {
            Tree -> Right_Child = Node;
        }
        else
        {
            add_Node(Tree -> Right_Child, Node);
        }
    }
    else if (Tree -> Data > Node-> Data)
    {
        if (Tree -> Left_Child == NULL)
        {
            Tree -> Left_Child = Node;
        }
        else
        {
            add_Node(Tree -> Left_Child, Node);
        }
    }
}
 
TreeNode* search_Node(TreeNode* Tree)
{
    if (Tree == NULL)
    {
        return NULL;
    }
 
    if (Tree -> Left_Child == NULL)
    {
        return Tree;
    }
    else
    {
        return search_Node(Tree -> Left_Child);
    }
}
 
TreeNode* search_Node(TreeNode* Tree, int data)
{
    if (Tree == NULL)
    {
        return NULL;
    }
   
    if (Tree->Data == data)
    {
        return Tree;
    }
    else if (Tree->Data > data)
    {
        return search_Node (Tree->Left_Child, data);
    }
    else
    {
        return search_Node (Tree->Right_Child,  data);
    }
}
TreeNode* remove_Node(TreeNode* Tree, TreeNode* Parent, int data)
{
    TreeNode* remove = NULL;
 
    if (Tree == NULL)
    {
        return NULL;
    }
 
    if (Tree->Data > data)
    {
        remove = remove_Node(Tree->Left_Child, Tree, data);
    }
 
    else if (Tree->Data < data)
    {
        remove = remove_Node(Tree->Right_Child, Tree, data);
    }
 
    else
    {
        remove = Tree;
 
        if (Tree->Left_Child == NULL && Tree->Right_Child == NULL)
        {
            if (Parent->Left_Child == Tree)
            {
                Parent->Left_Child = NULL;
            }
            else 
            {
                Parent->Right_Child = NULL;
            }
        }
        else
        {
            if (Tree->Left_Child != NULL && Tree->Right_Child != NULL) 
            {
                TreeNode* Node = search_Node( Tree->Right_Child );
 
                Node = remove_Node( Tree, NULL, Node->Data );
                Tree->Data = Node->Data;
            }
            else
            {
                TreeNode* Temp = NULL;
                if (Tree->Left_Child != NULL)
                {
                    Temp = Tree->Left_Child;
                }
                else 
                {
                    Temp = Tree->Right_Child;
                }
 
                if (Parent->Left_Child == Tree)
                {
                    Parent->Left_Child  = Temp;
                }
                else 
                {
                    Parent->Right_Child = Temp;
                }
            }
        }
    }
 
    return remove;
}
 
void PreorderPrint(TreeNode* Node)
{
    if(Node == NULL)
    {
        return;
    }
    cout << Node-> Data << " ";
    PreorderPrint(Node -> Left_Child);
    
    PreorderPrint(Node -> Right_Child);
}
void InorderPrint(TreeNode* Node)
{
    if(Node == NULL)
    {
        return;
    }
    
    InorderPrint(Node -> Left_Child);
    cout << Node-> Data << " ";
    InorderPrint(Node -> Right_Child);
}
void PostorderPrint(TreeNode* Node)
{
    if(Node == NULL)
    {
        return;
    }
    
    PostorderPrint(Node -> Left_Child);
    PostorderPrint(Node -> Right_Child);
    cout << Node-> Data << " ";
}
void main()
{
    TreeNode* Tree = create_Node(10);
    TreeNode* Node = NULL;
 
    add_Node(Tree, create_Node(2));
    add_Node(Tree, create_Node(98));
    add_Node(Tree, create_Node(37));
    add_Node(Tree, create_Node(15));
    add_Node(Tree, create_Node(8));
    add_Node(Tree, create_Node(5));
    add_Node(Tree, create_Node(4));
    add_Node(Tree, create_Node(76));
    add_Node(Tree, create_Node(17));
    add_Node(Tree, create_Node(194));
    
    Node = search_Node(Tree, 2);
    if(Node != NULL)
    {
        cout << "Node is Not NULL" << endl;
    }
    else
    {
        cout << "Node is NULL" << endl;
    }
 
    InorderPrint(Tree);
    cout << endl;
 
    Node = remove_Node( Tree, NULL, 15);
    PreorderPrint(Tree);
    cout << endl;
    InorderPrint(Tree);
    cout << endl;
    PostorderPrint(Tree);
    cout << endl;
 
    getch();
 
}

결과화면

출처

위키피디아

https://ko.wikipedia.org/wiki/%EC%9D%B4%EC%A7%84_%ED%83%90%EC%83%89_%ED%8A%B8%EB%A6%AC