컴공 일기176

비선형 자료구조 중 가장 Normal한 이진 트리(BinaryTree)를 구현했습니다. 기본적으로, 이진 트리는 자료 탐색이 굉장히 빠르다는 장점을 가지고 있죠. 그러기에, 컴퓨터에서 은근히 "트리"라는 자료를 굉장히 많이 가져다 씁니다.

개인적으로, 트리 중에 가장 끝판왕은 B-Tree가 아닌가 하는데, 이 B-Tree 기반의 주소록 구현은 취준 포트폴리오에 넣어도 경쟁력을 확보할 수 있습니다. 그만큼 어려운 자료구조입니다. 하지만, 그만큼 "효율성"은 극대된다는 것이... 그래서 B-Tree 기반의 주소록을 짤 줄 아는 개발자하고 모르는 개발자는 구분해서 볼 필요가 있다는 말이 나오는 걸까요? 

헤더 파일 ; BinaryTree.h

#ifndef BINARY_TREE_H

#define BINARY_TREE_H

#include <stdio.h>

#include <stdlib.h>

typedef struct tagSBTNode

{

    struct tagSBTNode* Left;

    struct tagSBTNode* Right;

    char Data;

}SBTNode;

SBTNode* SBT_CreateNode(char NewData);

void     SBT_DestroyNode(SBTNode* Node);

void     SBT_DestroyTree(SBTNode* Root);

void     SBT_PreorderPrintTree(SBTNode* Node);

void     SBT_InorderPrintTree(SBTNode* Node);

void     SBT_PostorderPrintTree(SBTNode* Node);

#endif

리소스 파일 ; BinaryTree.c

#include "BinaryTree.h"

SBTNode* SBT_CreateNode(char NewData)

{

    SBTNode* NewNode = (SBTNode*)malloc(sizeof(SBTNode));

    NewNode->Left = NULL;

    NewNode->Right = NULL;

    NewNode->Data = NewData;

    return NewNode;

}

void SBT_DestroyNode(SBTNode* Node)

{

    free(Node);

}

void SBT_DestroyTree(SBTNode* Node)

{

    if (Node == NULL)

        return;

    SBT_DestroyTree(Node->Left);

    SBT_DestroyTree(Node->Right);

    SBT_DestroyNode(Node);

}

void SBT_PreorderPrintTree(SBTNode* Node)

{

    if (Node == NULL)

        return;

    printf(" %c", Node->Data);

    SBT_PostorderPrintTree(Node->Left);

    SBT_PostorderPrintTree(Node->Right);

}

void SBT_InorderPrintTree(SBTNode* Node)

{

    if (Node == NULL)

        return;

    SBT_InorderPrintTree(Node->Left);

    printf(" %c", Node->Data);

    SBT_InorderPrintTree(Node->Right);

}

void SBT_PostorderPrintTree(SBTNode* Node)

{

    if (Node == NULL)

        return;

    SBT_PostorderPrintTree(Node->Left);

    SBT_PostorderPrintTree(Node->Right);

    printf(" %c", Node->Data);

}

소스 파일 ; Test_BinaryTree.c 

#include "BinaryTree.h"

int main()

{

    SBTNode* A = SBT_CreateNode('A');

    SBTNode* B = SBT_CreateNode('B');

    SBTNode* C = SBT_CreateNode('C');

    SBTNode* D = SBT_CreateNode('D');

    SBTNode* E = SBT_CreateNode('E');

    SBTNode* F = SBT_CreateNode('F');

    SBTNode* G = SBT_CreateNode('G');

    A->Left = B;

    B->Left = C;

    B->Left = D;

    A->Right = E;

    E->Left = F;

    E->Right = G;

    printf("PreorderPrinting...\n");

    SBT_PreorderPrintTree(A);

    printf("\n\n");

    printf("InorderPrinting...\n");

    SBT_InorderPrintTree(A);

    printf("\n\n");

    printf("PostorderPrinting...\n");

    SBT_PostorderPrintTree(A);

    printf("\n");

    SBT_DestroyNode(A);

    return 0;

}

실행결과 :

PreorderPrinting...

 A D B F G E

InorderPrinting...

 D B A F E G

PostorderPrinting...

 D B F G E A