트리(Tree)란?

트리란?

▶ 계층적인 구조를 나타내는 자료구조

▶ 리스트, 스택, 큐 등은 선형 구조이다.

▶ 트리는 부모-자식 관계의 노드들로 이루어진다.

▶ 응용 분야:

1) 계층적인 조직 표현

2) 컴퓨터 디스크의 디렉토리 구조

3) 인공지능에서의 결정 트리 (Decision Tree)

 

ex) 회사의 조직

트리의 예1 - 회사의 조직

 

ex) 파일 디렉토리 구조

트리의 예2 - 컴퓨터 디렉토리

 

ex) 결정 트리 (Decision Tree)

예시 - 골프에 대한 결정 트리

트리의 예3 - 결정 트리

 

이처럼, 계층적인 구조를 표시할 때 사용되는 자료구조가 트리이다.

 

트리에 대해 자세히 공부하려면 트리의 용어부터 알고 가야한다.

 

트리의 용어

▶ 노드(node): 트리의 구성요소

▶ 루트(root): 부모가 없는 노드

▶ 서브트리(subtree): 하나의 노드와 그 노드들의 자손들로 이루어진 트리

 

말로만 이해하려고 하면 어려우니, 그림을 보고 이해해보자.

 

여기서 노드는 A~J, 루트는 A 노드가 되겠다.

 

▶ 단말노드(terminal node): 자식이 없는 노드

▶ 비단말노드: 적어도 하나의 자식을 가지는 노드

 

위 그림에서 단말 노드는 E,F,G,H,I,G.

비단말노드는 A,B,C,D가 되겠다.

 

그리고 각각의 노드는 그 특징에 따라 붙는 명칭이 달라진다.

▶ 자식, 부모, 형제, 조상, 자손 노드

 

▶ 차수(degree): 노드가 가지고 있는 자식 노드의 개수

▶ 레벨(level): 트리의 각층의 번호

▶ 높이(height): 트리의 최대 레벨

 

그림을 보고 이해해보자.

 

여기서 A 노드는 B, C, D의 부모 노드라고 할 수 있다.

또한, B, C, D는 서로 형제 노드이다.

그리고 E, F, G는 B의 자식 노드라고 할 수 있다.

마지막으로 각 노드 오른쪽의 숫자는 차수이고, 위 트리의 높이는 3이다.

 

트리는 가족 직계도와 매우 유사한 면이 있음을 알 수 있다.

 

다른 예제를 알아보자.

▶ A는 루트 노드(node)이다.

▶ B는 D와 E의 부모 노드(parent node)이다.

▶ C는 B의 형제 노드(sibling node)이다.

▶ D와 E는 B의 자식노드(child node)이다.

▶ B의 차수(degree)는 2이다.

▶ 위의 트리의 높이(height)는 4이다.

 

트리의 종류

 

트리의 종류에는 이진 트리와 일반 트리가 있다.

 

이진 트리 (binary tree)

▶ 이진 트리란 모든 노드가 최대 2개의 서브 트리를 가지고 있는 트리이다.

▶ 서브트리는 공집합일 수 있다.

▶ 이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재한다.

▶ 모든 노드의 차수가 2 이하가 된다 -> 구현하기 편리함

▶ 이진 트리에는 서브 트리간의 순서가 존재한다.

 

이진 트리 검증

▶ 이진 트리는 공집합이다.

▶ 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다.

이진 트리의 서브 트리들은 모두 이진 트리이어야 한다.

 

이진 트리의 성질

1) 노드의 개수가 n개이면 간선의 개수는 n-1

 

2) 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2^h-1개의 노드를 가진다.

3) n개의 노드를 가지는 이진트리의 높이

 

▶ 최대

▶ 최소

 

 

 

이진 트리의 분류

▶ 포화 이진 트리(full binary tree)

▶ 완전 이진 트리(complete binary tree)

▶ 기타 이진 트리

 

포화 이진 트리 (full binary tree)

▶ 용어 그대로 트리의 각 레벨에 노드가 꽉 차있는 이진트리를 의미한다.

▶ 포화 이진 트리에는 다음과 같이 각 노드에 번호를 붙일 수 있다.

 

완전 이진 트리 (complete binary tree)

▶ 레벨 1부터 k-1까지는 노드가 모두 채워져 있고, 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리

▶ 포화 이진 트리와 노드 번호가 일치

 

이진 트리의 표현

▶ 배열을 이용하는 방법

▶ 링크(포인터)를 이용하는 방법

 

먼저, 배열 표현법을 이용한 방법을 알아보자.

 

▶ 배열 표현법

모든 이진 트리를 포화 이진 트리라고 가정하고, 각 노드에 번호를 붙여서

그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

 

▶ 부모와 자식 인덱스 관계

노드 i의 부모 노드 인덱스 = i/2

노드 i의 왼쪽 자식 노드 인덱스 = 2i

노드 i의 오른쪽 자식 노드 인덱스 = 2i + 1

 

그 다음, 링크 표현법을 알아보자.

 

▶ 링크 표현법

포인터를 이용하여 부모노드가 자식노드를 가리키게 하는 방법

 

링크를 구현할 때, 노드는 구조체로 표현하고, 링크는 포인터로 표현한다.

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

 

위 구조체를 바탕으로

아래의 구조를 가진 트리를 링크 표현법 프로그램으로 간단하게 짜보자.

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

void main() {
    TreeNode *n1, *n2, *n3:

    n1 = (TreeNode *)malloc(sizeof(TreeNode));
    n2 = (TreeNode *)malloc(sizeof(TreeNode));
    n3 = (TreeNode *)malloc(sizeof(TreeNode));

    n1->data = 10;  // 첫번째 노드를 설정한다.
    n1->left = n2;
    n1->right = n3;

    n2->data = 20;  // 두번째 노드를 설정한다.
    n2->left = NULL;
    n2->right = NULL;

    n3->data = 30;  // 세번째 노드를 설정한다.
    n3->left = NULL;
    n3->right = NULL;
}

 

이진 트리의 순회

▶ 순회(Traversal): 트리의 노드들을 체계적으로 방문하는 것

▶ 3가지의 기본적인 순회방법

전위순회(preorder traversal): VLR - 자손노드보다 루트노드를 먼저 방문한다.

중위순회(inorder traversal): LVR - 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문한다.

후위순회(postorder traversal): LRV - 루트노드보다 자손을 먼저 방문한다.

 

 

전위 순회 (preorder traversal)

▶ 루트 노드를 방문한다.

▶ 왼쪽 서브트리를 방문한다.

▶ 오른쪽 서브트리를 방문한다.

 

전위 순회 알고리즘

▶ 순환 호출을 이용한다.

'

전위 순회 응용

▶ (예) 구조화된 문서 출력

전위 순회의 예 - 구조화된 문서 출력

 

 

중위 순회 (inorder traversal)

▶ 왼쪽 서브트리를 방문한다.

▶ 루트 노드를 방문한다.

▶ 오른쪽 서브트리를 방문한다.

 

중위 순회 알고리즘

▶ 순환 호출을 이용한다.

 

중위 순회 응용

▶ (예) 수식 트리

중위 순회의 예 - 수식 트리

 

 

후위 순회 (postorder traversal)

▶ 왼쪽 서브트리를 방문한다.

▶ 오른쪽 서브트리를 방문한다.

▶ 루트 노드를 방문한다.

 

후위 순회 알고리즘

▶ 순환 호출을 이용한다.

 

후위 순회 응용

▶ (예) 디렉토리 용량 계산

후위 순회의 예 - 디렉토리 용량 계산

 

각 순회 방법을 C언어로 표현해보자.

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

TreeNode n1 = {1, NULL, NULL};
TreeNode n2 = {4, &n1, NULL};
TreeNode n3 = {16, NULL, NULL};
TreeNode n4 = {25, NULL, NULL};
TreeNode n5 = {20, &n3, &n4};
TreeNode n6 = {15, &n2, &n5};
TreeNode *root = &n6;

// 중위 순회
void inorder(TreeNode *root) {
    if (root) {
        inorder(root->left);  // 왼쪽 서브트리 순회
        printf("%d ", root->data); // 노드 방문
        inorder(root->right); // 오른쪽 서브트리 순회
    }
}

// 전위 순회
void preorder(TreeNode *root) {
    if (root) {
        printf("%d ", root->data); // 노드 방문
        preorder(root->left);  // 왼쪽 서브트리 순회
        preorder(root->right); // 오른쪽 서브트리 순회
    }
}

// 후위 순회
void postorder(TreeNode *root) {
    if (root) {
        postorder(root->left);  // 왼쪽 서브트리 순회
        postorder(root->right); // 오른쪽 서브트리 순회
        printf("%d ", root->data); // 노드 방문
    }
}

int main() {
    printf("Inorder traversal: ");
    inorder(root);
    printf("\n");

    printf("Preorder traversal: ");
    preorder(root);
    printf("\n");

    printf("Postorder traversal: ");
    postorder(root);
    printf("\n");

    return 0;
}

 

레벨 순회 (level order)

▶ 레벨 순회는 각 노드를 레벨 순으로 검사하는 순회 방법이다.

▶ 지금까지의 순회 방법이 스택을 사용했던 것에 비해, 레벨 순회는 큐를 사용하는 순회 방법이다.

레벨 순회

 

레벨 순회 알고리즘

레벨 순회 알고리즘

 

위 알고리즘을 바탕으로 레벨 순회 프로그램을 C언어로 작성해보자.

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

#define MAX_QUEUE_SIZE 100

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;

// 큐 정의
typedef TreeNode* Element;
typedef struct {
    Element queue[MAX_QUEUE_SIZE];
    int front, rear;
} QueueType;

void init_queue(QueueType *q) {
    q->front = q->rear = 0;
}

int is_empty(QueueType *q) {
    return (q->front == q->rear);
}

int is_full(QueueType *q) {
    return ((q->rear + 1) % MAX_QUEUE_SIZE == q->front);
}

void enqueue(QueueType *q, Element item) {
    if (is_full(q)) {
        fprintf(stderr, "큐가 포화상태입니다.\n");
        exit(1);
    }
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = item;
}

Element dequeue(QueueType *q) {
    if (is_empty(q)) {
        fprintf(stderr, "큐가 공백상태입니다.\n");
        exit(1);
    }
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->queue[q->front];
}

// 레벨 순회
void level_order(TreeNode *ptr) {
    QueueType q;
    init_queue(&q); // 큐 초기화
    if (ptr == NULL) return;
    enqueue(&q, ptr);
    while (!is_empty(&q)) {
        ptr = dequeue(&q);
        printf(" [%d] ", ptr->data);
        if (ptr->left) 
            enqueue(&q, ptr->left);
        if (ptr->right)
            enqueue(&q, ptr->right);
    }
}

// 트리 노드 정의
TreeNode n1 = {1, NULL, NULL};
TreeNode n2 = {4, &n1, NULL};
TreeNode n3 = {16, NULL, NULL};
TreeNode n4 = {25, NULL, NULL};
TreeNode n5 = {20, &n3, &n4};
TreeNode n6 = {15, &n2, &n5};
TreeNode *root = &n6;

int main() {
    printf("레벨 순회=");
    level_order(root);
    printf("\n");
    
    return 0;
}

 

위 코드는 큐를 사용하여, 레벨 별로 노드들을 방문하고, enqueue 작업과 dequeue 작업을 수행한다.

 

글이 너무 길어져서 이진 트리 연산과 이진 탐색 트리 연산은 다음 게시글에 작성하도록 하겠다.

 

 

다음에 계속...