[C언어 소스] 이진 탐색 트리의 운행

안녕하세요. 언제나 휴일입니다.

이번에는 이진 탐색 트리(Binary Search Tree)의 운행에 관해서 다룰게요.

이진 탐색 트리에서는 자료를 보관할 때 부모보다 작은 값을 갖는 자료는 부모의 왼쪽 서브 트리에 매달고 큰 값을 갖는 자료는 부모의 오른쪽 서브 트리에 매다는 이진 트리입니다. 그리고 이진 탐색 트리에서는 같은 값을 갖는 자료는 보관하지 않습니다. 이처럼 매달면 서브 트리도 이진 탐색 트리인 특징을 갖습니다.

binary search tree = { root, sub trees}

sub tree is binary search tree, left son’ s data <parent’s data > right son’s data,

MAX[N(sub tree)]=2

이진 탐색 트리
이진 탐색 트리

이진 탐색 트리의 모든 노드를 방문할 때도 재귀적인 방법으로 문제를 해결할 수 있습니다. 만약 루트를 먼저 방문한 후에 왼쪽 서브 트리를 방문하고 오른쪽 서브 트리를 방문하면 전위 순회(Pre Order Travel) 혹은 전위 운행이라고 말합니다.

위의 이진 탐색 트리에서 전위 순회하면 방문 순서는 10, 6, 5, 3, 9, 15, 14, 25, 19와 같습니다. 언제나 부모는 자식들보다 먼저 방문하고 있음을 알 수 있습니다.

PreOrderTravel(sr:서브 트리의 루트 노드, doit: 수행할 알고리즘)

조건(sr IsEqual null)

종료

    doit(sr)

    PreOrderTravel (sr의 왼쪽 자식 노드, doit)

    PreOrderTravel (sr의 오른쪽 자식 노드, doit)

왼쪽 서브 트리를 방문한 후에 오른쪽 서브 트리를 방문한 후에 마지막으로 루트를 방문하는 것을 후위 순회(Post Order Travel)혹은 후위 운행이라고 말합니다.

위의 이진 탐색 트리에서 후위 순회하면 방문 순서는 3, 5, 9, 6, 14, 19, 25, 15, 10과 같습니다. 언제나 부모는 자식들보다 나중에 방문하고 있음을 알 수 있습니다.

PostOrderTravel(sr:서브 트리의 루트 노드, doit: 수행할 알고리즘)

조건(sr IsEqual null)

종료

    PostOrderTravel (sr의 왼쪽 자식 노드, doit)

    PostOrderTravel(sr의 오른쪽 자식 노드, doit)

    doit(sr)

왼쪽 서브 트리를 방문한 후에 루트를 방문하고 오른쪽 서브 트리를 방문하는 것을 중위 순회(In Order Travel) 혹은 중위 운행이라고 말합니다.

위의 이진 탐색 트리에서 중위 순회하면 방문 순서는 3, 5, 6, 9, 10, 14, 15, 19, 15와 같습니다. 언제나 부모는 왼쪽 자식들보다 나중에 방문하고 오른쪽 자식들보다 먼저 방문함을 알 수 있습니다.

InOrderTravel(sr:서브 트리의 루트 노드, doit: 수행할 알고리즘)

조건(sr IsEqual null)

종료

     InOrderTravel (sr의 왼쪽 자식 노드, doit)

    doit(sr)

     InOrderTravel (sr의 오른쪽 자식 노드, doit)

다음은 예제 코드의 실행 화면입니다.

이진 탐색 트리 운행 실행 결과
이진 탐색 트리 운행

소스 코드

//이진 탐색 트리 운행
#include <stdio.h>
#include <stdlib.h>

typedef struct Node//노드 정의
{
    int data;
    struct Node *lchild;
    struct Node *rchild;
}Node;

typedef Node *Tree;//트리 형식명 정의

Node *NewNode(int data);//노드 생성
void InitTree(Tree *bst);//트리 초기화
int AddData(Tree *bst, int data); //데이터 보관
void Preorder(Node *sr);//전위 순위 운행
void Inorder(Node *sr);//중위 순위 운행
void Postorder(Node *sr);//후위 순위 운행
void ClearTree(Tree *bst);//트리 해제
int main(void)
{
    Tree tree;

    InitTree(&tree);//트리 초기화

                    //트리에 자료 보관
    AddData(&tree, 10);
    AddData(&tree, 6);
    AddData(&tree, 9);
    AddData(&tree, 5);
    AddData(&tree, 15);
    AddData(&tree, 25);
    AddData(&tree, 3);
    AddData(&tree, 19);
    AddData(&tree, 14);

    //트리에 보관한 자료 확인
    printf("전위 순위 운행:");
    Preorder(tree);
    printf("\n중위 순위 운행:");
    Inorder(tree);
    printf("\n후위 순위 운행:");
    Postorder(tree);

    //트리 해제
    ClearTree(&tree);
    printf("\n");
}
Node *NewNode(int data)
{
    Node *now = (Node *)malloc(sizeof(Node));
    now->data = data;
    now->lchild = now->rchild = NULL;
    return now;
}

void InitTree(Tree *bst)
{
    *bst = NULL;
}

int AddData(Tree *bst, int data)
{
    Node *seek = *bst;
    int gap = 0;
    if (seek == NULL)
    {
        (*bst) = NewNode(data);
        return 1;//보관 성공 반환
    }
    while (1)
    {
        gap = seek->data - data;
        if (gap == 0)//이미 같은 값의 데이터를 보관했음
        {
            return 0;//보관 실패 반환
        }
        if (gap>0)//기존 데이터가 클 때(들어갈 데이터가 작을 때)
        {
            if (seek->lchild)//왼쪽에 자식이 이미 있으면
            {
                seek = seek->lchild;//seek를 왼쪽 자식으로 설정
            }
            else
            {
                seek->lchild = NewNode(data);//왼쪽 자식으로 새로운 노드를 설정
                return 1;//보관 성공 반환
            }
        }
        else//기존 데이터가 작을 때(들어갈 데이터가 클 때)
        {
            if (seek->rchild)//오른쪽에 자식이 이미 있으면
            {
                seek = seek->rchild;//seek를 오른쪽 자식으로 설정
            }
            else
            {
                seek->rchild = NewNode(data);//오른쪽 자식으로 새로운 노드를 설정
                return 1;//보관 성공 반환
            }
        }

    }
    return 1;
}
void Preorder(Node *sr)//전위 순위 운행
{
    if (sr)
    {
        printf("%d ", sr->data);
        Preorder(sr->lchild);
        Preorder(sr->rchild);
    }
}
void Inorder(Node *sr)//중위 순위 운행
{
    if (sr)
    {
        Inorder(sr->lchild);
        printf("%d ", sr->data);
        Inorder(sr->rchild);
    }
}
void Postorder(Node *sr)//후위 순위 운행
{
    if (sr)
    {
        Postorder(sr->lchild);
        Postorder(sr->rchild);
        printf("%d ", sr->data);
    }
}
void Dispose(Node *sr);
void ClearTree(Tree *bst)
{
    Dispose(*bst);
    *bst = 0;
}
void Dispose(Node *sr)//후위 순위로 해제
{
    if (sr)
    {
        Dispose(sr->lchild);
        Dispose(sr->rchild);
        free(sr);
    }
}

C언어 소스