자료구조 8강 트리의 개요, 소스 코드

트리(Tree)

고급 자료구조로 분류되는 트리는 계층적 관계(Hierarchical Relationship)를 표현하는 자료구조.

비선형 자료구조이기도 하다.

가지를 늘려가며 뻗어간다는 모양새에 근거하여 '트리'라 명명.

트리의 예시

컴퓨터의 디렉터리 구조

집안의 족보나 기업 및 정부의 조직도

트리의 기본적인 용어

노드(node) - 트리의 구성요소.

간선(edge) - 노드와 노드를 연결하는 연결선.

루트 노드(root node) - 트리 구조에서 최상위에 존재하는 A와 같은 노드.

단일 노드(terminal node) - 아래로 또 다른 노드가 연결되어 있지 않은 노드, 잎사귀 노드라고도 불림.

내부 노드(internal node) - 단일 노드를 제외한 모든 노드, 비단말 노드라고도 불림.

노드 간에는 부모(parent), 자식(child), 형제(sibling) 관계가 성립.

각 층별로 숫자를 매기고 '레벨'이라 부르고 트리의 최고 레벨을 '높이'라 부름.

이진 트리(Binary Tree) - 자식 노드가 두 개씩 달린 트리

루트 노드를 중심으로 두 개의 서브 트리로 나뉘어짐.

나뉘어진 두 서브 트리도 모두 이진 트리.

노드가 위치할 수 있는 곳에 노드가 위치하지 않는다면, 공집합(empty set) 노드가 존재하는 것으로 간주하여, 이진 트리로 판단.

서브 트리(Sub Tree) - 큰 트리에 속하는 작은 트리

포화 이진 트리(full binary tree) - 모든 레벨이 꽉 차있는 이진 트리, 노드를 더 추가하려면 레벨을 늘려야 함.

완전 이진 트리(complete binary tree) - 모든 레벨이 꽉 찬 상태는 아니지만 빈 틈 없이 노드가 채워진 이진 트리.

이진트리의 소스 구현

// BinaryTree.h

#ifndef     __BINARY_TREE_H_
#define     __BINARY_TREE_H_

typedef int BTData;

typedef struct _bTreeNode
{
    BTData data;
    struct _bTreeNode * left;
    struct _bTreeNode * right;
} BTreeNode;

BTreeNode * MakeBTreeNode(void);
BTData GetData(BTreeData * bt);
void SetData(BTreeNode * bt, BTData data);

BTreeNode * GetLeftSubTree(BTreeNode * bt);
BTreeNode * GetRightSubTree(BTreeNode * bt);

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub);
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub);

#endif

// BinaryTree.c

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

BTreeNode * MakeBTreeNode(void)
{
    BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
    nd->left = NULL;
    nd->right = NULL;
    return nd;
}

BTData GetData(BTreeNode * bt)
{
    return bt->data;
}

void SetData(BTreeNode * bt, BTData data)
{
    bt->data = data;
}

BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
    return bt->left;
}

BTreeNode * GetRightSubTree(BTreeNode * bt)
{
    return bt->right;
}

void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
    if(main->left != NULL)
        free(main->left);

    main->left = sub;
}

#include <stdio.h>
#include "BinaryTree.h"

int main(void)
{
    BTreeNode * bt1 = MakeBTreeNode();
    BTreeNode * bt2 = MakeBTreeNode();
    BTreeNode * bt3 = MakeBTreeNode();
    BTreeNode * bt4 = MakeBTreeNode();

    SetData(bt1, 1);
    SetData(bt2, 2);
    SetData(bt3, 3);
    SetData(bt4, 4);

    MakeLeftSubTree(bt1, 2);
    MakeLeftSubTree(bt1, 3);
    MakeLeftSubTree(bt3, 3);
    MakeLeftSubTree(bt4, 4);

    MakeLeftSubTree(bt1, bt2);
    MakeRightSubTree(bt1, bt3);
    MakeLeftSubTree(bt2, bt4);

    printf("%d \n", GetDate(GetLeftSubTree(bt1)));

    printf("%d \n", GetDate(GetLeftSubTree(GetLeftSubTree(bt1))));

    return 0;
}

출력 결과

2
4

이진 트리의 순회 세 가지

• 전위 순회(Preorder Traversal)
• 중위 순회(Inorder Traversal)
• 후위 순회(Postorder Traversal)

코드 구현

#include <stdio.h>
#include "BinaryTree.h"

void InorderTraverse(BTreeNode *bt) // 이진 트리 전체를 중위 순회하는 함수
{
    if(bt == NULL)
        return;

    InorderTraverse(bt->left);  // 1단계 왼쪽 서브 트리의 순회
    printf("%d \n", bt->data);  // 2단계 루트 노드의 방문
    InorderTraverse(bt->right); // 3단계 오른쪽 서브 트리의 순회
}

int main(void)
{
    BTreeNode * bt1 = MakeBTreeNode();
    BTreeNode * bt2 = MakeBTreeNode();
    BTreeNode * bt3 = MakeBTreeNode();
    BTreeNode * bt4 = MakeBTreeNode();

    SetData(bt1, 1);
    SetData(bt2, 2);
    SetData(bt3, 3);
    SetData(bt4, 4);

    MakeLeftSubTree(bt1, bt2);
    MakeRightSubTree(bt1, bt3);
    MakeLeftSubTree(bt2, bt4);

    InorderTraverse(bt1);
    return 0;
}

결과 출력

4
2
1
3

수식 트리(Expression Tree)

이진 트리의 일종.

이진 트리를 이용해서 수식을 표현해 놓은 것이 수식 트리이다.

코드 구현

int main(void)
{
    int result = 0;
    result = 7 + 4 * 2 - 1; 
}

컴파일러는 위와 같은 수식 코드를 처리하기 위해 수식 트리를 이용한다.

컴파일러는 수식의 이해를 위해 수식을 수식 트리로 재표현.

루트 노드에 저장된 연산자의 연산을 하되, 두 개의 자식 노드에 저장된 두 피연산자를 대상으로 연산을 한다.