Tree(2) - Binary Tree

이진 트리는 노드의 최대 차수가 2인 트리이다.

Binary Tree는 데이터를 담는 용도로로는 사용하기 곤란하지만, 이런 구조를 이용한 훌륭한 알고리즘들이 개발되어 있다.

수식 이진 트리(Expression Binary Tree)와 이진 탐색 트리(Binary Search Tree)가 대표적인 알고리즘이다.

 

포화 이진 트리(Full Binary Tree) : 잎 노드를 제외한 모든 노드가 자식을 둘씩 가진 이진 트리

완전 이진 트리(Complete Binary Tree) : 잎 노드들이 트리의 왼쪽부터 차곡차곡 채워진 트리

높이 균형 트리(Height Balanced Tree) : 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 1이상 차이나지 않는 이진 트리

완전 높이 균형 트리(Completely Height Balanced Tree) : 루트 노드를 기준으로 왼쪽 하위 트리와 오른쪽 하위 트리의 높이가 같은 이진 트리

 

이진 트리의 순회 방법

- 전위 순회(Preorder Traversal) : root, left, right

- 중위 순회(Inorder Traversal) : left, root, right

- 후위 순회(Postorder Traversal) : left, right, root

 

// gcc -o Test_BinaryTree.exe Test_BinaryTree.c BinaryTree.c; ./Test_BinaryTree.exe

#include <stdio.h>
#include <stdlib.h>

typedef char ElementType;

typedef struct tagSBTNode 
{
    struct tagSBTNode* Left;
    struct tagSBTNode* Right;

    ElementType Data;
} SBTNode;

SBTNode* SBT_CreateNode( ElementType 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_PreorderPrintTree( Node->Left );

    /*  오른쪽 하위 트리 출력 */
    SBT_PreorderPrintTree( 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 );
}

int main( void )
{
    /*  노드 생성 */
    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->Right = D;

    A->Right = E;
    E->Left  = F;
    E->Right = G;
    
    /*  트리 출력 */
    printf("Preorder ...\n");
    SBT_PreorderPrintTree( A );
    printf("\n\n");

    printf("Inorder ... \n");
    SBT_InorderPrintTree( A );
    printf("\n\n");

    printf("Postorder ... \n");
    SBT_PostorderPrintTree( A );
    printf("\n");

    /*  트리 소멸시키기 */
    SBT_DestroyTree( A );

    return 0;
}