트리

트리

정의

• 계층적인 구조를 나타내는 자료구조
• 비선형 자료구조 (스트 , 스택, 큐 는 선형 구조임.)
• 트리는 부모 - 자식 관계의 노드들로 이루어짐.
• 1개 이상의 노드를 갖는 집합으로 노드들은 아래 조건을 만족함.

• root 라고 불리는 특별한 노드가 있음
• 다른 노드들은 원소가 중복되지 않는 n 개의 부속 트리 (subtree)임.

저장법

n-링크 표현법

• 노드에 n개의 링크를 두고 자식의 개수만큼 링크에 저장한다. 모든 노드는 자식 노드 수에 관계없이 최대 n개의 링크를 갖는다. 각 링크는 부속 트리가 저장된 곳을 링크한다.

왼쪽자식노드 - 오른쪽 형제노드 표현방법

(출처 : https://apape1225.tistory.com/57)

• 첫번째 링크는 첫번째 자식 노드를 표현 하고, 두번째 링크는 자신의 오른쪽 형제 노드를 표현한다,

용어

• 정점 (노드) : 트리의 구성 요소
• 루트 : 부모가 없는 노드
• 서브 트리 : 하나의 노드와 그 노드들의 자손들로 이루어진 트리
• 단말 노드 (terminal node) : 자식이 없는 노드
• 비 단말 노드 : 적어도 하나의 자식을 가지는 노드
• 차수 : 루트 노드가 가지고 있는 자식 노드의 개수
• 진출 차수 : 방향그래프에서 사용되는 용어로, 한 노드에서 외부로 향하는 간선의 수
• 진입 차수 : 방향그래프에서 사용되는 용어로 외부 노드에서 들어온 간선의 수

종류

이진 트리

정의

• 모든 노드가 2개의 서브 트리를 가지고 있는 트리 (서브 트리는 공집합일 수 있음.)
• 이진트리의 노드는 최대 2개까지 자식 노드가 존재
• 모든 노드의 차수는 2 이하가 됨 $$\Rightarrow$$ 구현하기 편리함
• 이진 트리에는 서브트리간의 순서가 존재함.
• 노드가 $$n$$개면 간선은 $$n-1$$개이다.
• 높이가 $$h$$인 이진트리의 경우, 최소 $$h$$개의 노드를 가지며 최대 $$2^h - 1$$개의 노드를 가진다.
• $$n$$개의 노드를 가지는 이진 트리의 높이는 최대 $$n$$, 최소 $$log_2(n-1)$$이다.

분류

• 포화 이진트리
  • 용어 그대로 트리의 각 레벨에 노드가 꽉차 있는 이진 트리
  • 전체 노드의 개수 : $$2^k - 1$$

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

• 기타 이진트리

구현 방식

배열 표현법

• 모든 이진트리를 포화 이진트리라고 가정하고 각 노드에 번호를 붙여서 그 번호를 배열의 인덱스로 삼아 노드의 데이터를 배열에 저장하는 방법

단점

• skewed 이진트리처럼 깊이에 비해 노드 수가 적은 경우 기억 공간 활용률이 낮다.
• 트리의 최대 깊이를 대비하여 많은 기억 장소를 확보해야 하고, 트리가 예상보다 커지면 프로그램 수행을 종료해야 한다.

부모와 자식 인덱스 관계

• 노드 i의 부모 노드 인덱스 : i / 2
• 노드 i의 왼쪽 자식 노드 인덱스 : 2i
• 노드 i의 오른쪽 자식 노드 인덱스 : 2i + 1

링크 표현법

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

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left, *right;
} TreeNode;
//              n1
//           / |
//          n2  n3
int main(void)
{
    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;
    free(n1); free(n2); free(n3);
    return 0;
}

이진 트리의 순회

전위 순회

• 자손 노드보다 루트 노드를 먼저 방문
• void preorder(TreeNode *root) { if (root != NULL) { printf("[%d] ", root->data); // 노드 방문 preorder(root->left);// 왼쪽서브트리 순회 preorder(root->right);// 오른쪽서브트리 순회 } }

중위 순회

• 왼쪽 자손, 루트, 오른쪽 자손 순으로 방문
• void inorder(TreeNode *root) { if (root != NULL) { inorder(root->left);// 왼쪽서브트리 순회 printf("[%d] ", root->data); // 노드 방문 inorder(root->right);// 오른쪽서브트리 순회 } }

후위 순회

• 루트노드보다 자손을 먼저 방문
• 왼쪽 서브트리 방문 하고, 오른쪽 서브트리 방문 후 루트 노드를 방문
• void postorder(TreeNode *root) { if (root != NULL) { postorder(root->left);// 왼쪽서브트리 순회 postorder(root->right);// 오른쪽서브트리순회 printf("[%d] ", root->data); // 노드 방문 } }

반복 순회

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

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

#define SIZE 100
int top = -1;
TreeNode *stack[SIZE];

void push(TreeNode *p)
{
    if (top < SIZE - 1)
        stack[++top] = p;
}

TreeNode *pop()
{
    TreeNode *p = NULL;
    if (top >= 0)
        p = stack[top--];
    return p;
}

void inorder_iter(TreeNode *root) /* inoder () */
{
    while (1) {
        for (; root; root = root->left)
            push(root);
        root = pop();
        if (!root) break;
        printf("[%d] ", root->data);
        root = root->right;
    }
}

void preorder_iter(TreeNode *root)
{
    push(root);
    while(1){
        root = pop();
        if(!root) break;
        printf("[%d] ", root -> data);
        push(root -> right);
        push(root -> left);
    }
}

void postorder_iter(TreeNode *root)
{
    /*  source implementation? */
}
//          15
//       4         20
//    1          16  25
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(void)
{
    printf("중위 순회=");
    inorder_iter(root);
    printf("\n");
    printf("선위 순회=");
    preorder_iter(root);
    printf("\n");
  printf("후위 순회=");
    postorder_iter(root);
    printf("\n");
    return 0;
}

레벨 순회

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

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

// ================ 원형큐 코드 시작 =================
#define MAX_QUEUE_SIZE 100
typedef TreeNode * element;
typedef struct { // 큐 타입
    element  data[MAX_QUEUE_SIZE];
    int  front, rear;
} QueueType;

// 오류 함수
void error(char *message)
{
    fprintf(stderr, "%s\n", message);
    exit(1);
}

// 공백 상태 검출 함수
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))
        error("큐가 포화상태입니다");
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->data[q->rear] = item;
}

// 삭제 함수
element dequeue(QueueType *q)
{
    if (is_empty(q))
        error("큐가 공백상태입니다");
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    return q->data[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);
    }
}
//          15
//       4         20
//    1          16  25
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(void)
{
    printf("레벨 순회=");
    level_order(root);
    printf("\n");
    return 0;
}