이진 탐색 트리(Binary Search Tree) 소스 코드

이전 게시물에서 이진 탐색 트리의 개념을 설명하였다.

코드로 옮기기 전, insert에 대한 코드는 아래와 같이 작성하면 된다.

insert(number X, node N)

if X가 노드 N에 있는 숫자보다 작다면

if N의 왼쪽 자식이 없다면

X를 포함하는 새 노드를 만든 뒤, N의 왼쪽 자식으로 만든다.

else

insert(X, N의 왼쪽 자식)

else X가 노드 N에 있는 숫자보다 크다면

if N의 오른쪽 자식이 없다면

X를 포함하는 새 노드를 만든 뒤, N의 오른쪽 자식으로 만들기

else

insert(X, N의 오른쪽 자식)

소스코드는 다음과 같다.

소스 코드를 검증하기 위해 순회 코드를 넣어 두었다.

< BinarySearchTree.c >

#include <stdio.h>
#include <stdlib.h>
 
typedef struct _map
{
    int key;
    struct _map *left;
    struct _map *right;
}map;
 
typedef struct _point
{
    map *root;
}point;
 
 
int init(int val, point *pt)
{
    map *newNode = (map*)malloc(sizeof(map));
    newNode->key = val;
    newNode->left = NULL;
    newNode->right = NULL;
    pt->root = newNode;
    return 1;
}
 
int insert(int val, point *pt)
{
    point *temp = pt;
 
    if (val < temp->root->key)
    {
        if (temp->root->left == NULL)
        {
            map *newNode = (map*)malloc(sizeof(map));
            temp->root->left = newNode;
            newNode->key = val;
            newNode->left = NULL;
            newNode->right = NULL;
        }
 
        else
        {
            insert(val, (point*) &(temp->root->left));
        }
    }
 
    // val이 노드 N에 있는 숫자보다 크다면
    else if (val > temp->root->key)
    {
        if (temp->root->right == NULL)
        {
            map *newNode = (map*)malloc(sizeof(map));
            temp->root->right = newNode;
            newNode->key = val;
            newNode->left = NULL;
            newNode->right = NULL;
        }
        else
        {
            insert(val, (point*) &(temp->root->right));
        }
        
    }
 
    return 1;
}
 
typedef void VisitFuncPtr(int data); // == void (*VisitFuncPtr)(BTData data);
void ShowData(int data)
{
    printf("%d ", data);
}
 
void PreorderTraverse(point *bt, VisitFuncPtr action)
{
    if (bt->root == NULL)
        return;
 
    action(bt->root->key);
    PreorderTraverse((point*)&(bt->root->left), action);
    PreorderTraverse((point*)&(bt->root->right), action);
}
 
void InorderTraverse(point *bt, VisitFuncPtr action)
{
    if (bt->root == NULL)
        return;
 
    InorderTraverse((point*)&(bt->root->left), action);
    action(bt->root->key);
    InorderTraverse((point*)&(bt->root->right), action);
}
 
void PostorderTraverse(point *bt, VisitFuncPtr action)
{
    if (bt->root == NULL)
        return;
 
    PostorderTraverse((point*)&(bt->root->left), action);
    PostorderTraverse((point*)&(bt->root->right), action);
    action(bt->root->key);
}
 
int main()
{
    point pt;
    int n,val, cnt = 0;
 
    // 몇개의 트리를 넣을지 입력
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &val);
 
        if (i == 0)
            init(val, &pt);
        else
            insert(val, &pt);
    }
 
    printf("전위 순회 :: ");
    PreorderTraverse(&pt, ShowData);
    printf("\n");
 
    printf("중위 순회 :: ");
    InorderTraverse(&pt, ShowData);
    printf("\n");
 
    printf("후위 순회 :: ");
    PostorderTraverse(&pt, ShowData);
    printf("\n");
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

< 결과 화면 >