6 minute read

1. 트리의 개념

  • 노드 : 간선과 함께 트리를 구성하는 것
  • 루트 노드 : 계층적인 구조에서 가장 높은 곳에 있는 노드
  • 서브트리: root node를 제외하는 나머지 node
  • 간선(edge 에지) : tree에서 root와 subtree를 연결하는 선
  • parent node
  • child node
  • sibling
  • ancestor node : 임의의 노드 하위에서 루트 노드까지의 경로를 이루고 있는 노드들
  • descendent node : 임의의 노드 하위에 연결된 모든 노드들, 즉 어떤 node의 subtree에 속하는 모든 node들
  • terminal node : child node가 없는 node
  • nonterminal node : child node가 있는 node
  • Degree(차수) of node : 어떤 node가 가지고 있는 child node의 수
  • Degree of tree : tree가 가지고 있는 node의 차수 중에서 가장 큰 값
  • Level : tree 각 층의 번호
  • Height : tree가 가지고 있는 최대 level

2. 이진 트리

  • Binary tree : 공집합이거나, root, left subtree, and right subtree 구성된 node들의 유한 집합. 각 node가 최대 2개의 child node를 갖는 tree. 즉 각 node는 자식이 없거나 한 개 또는 두 개이다.

이진트리의 subtree는 모두 이진트리다.

이진트리의 성질

이진 트리의 노드의 개수가 n이고 높이가 h일 때,

이진 트리의 성질    
이진트리의 간선의 개수 $n - 1$  
이진트리의 노드의 개수 $h \leq$ 이진트리의 노드의 개수 $\leq 2^h - 1$ 최소 : 한 레벨에 하나의 노드가 있을 때, 최대 : 포화 이진트리
이진트리의 높이 $[\log_2(n + 1)] + 1 \leq$ 이진트리의 높이 $\leq n$  
트리의 null의 개수 $n+1$  
leaf node의 개수 2개 child node를 가진 node의 개수 + 1  

이진트리의 분류

이진 트리의 분류 정의 특성
포화 이진트리(full binary tree) 트리의 각 레벨에 노드가 꽉 차있는 이진 트리 모든 내부 노드가 두 개의 자식 노드를 가지고 있으며, 모든 리프 노드가 같은 레벨에 있는 이진 트리
완전 이진트리(complete binary tree) 높이가 k인 트리에서 레벨 1부터 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리

추상 자료형

데이터 : node의 집합. 공집합이거나, 루트노드와 왼쪽 서브트리, 오른쪽 서브트리로 구성됨. 모든 서브트리도 이진트리이어야 함.

연산 - init() : 이진트리를 초기화한다.
    - is_empty() : 이진트리가 공백상태인지 확인한다.
    - create_tree(e, left, right) : 이진트리 left와 right를 각각 왼족과 오른쪽 자식으로하고 e를 루트로 하는 이진트리를 생성한다.
    - get_root() : 이진트리의 루트 노드를 반환한다.
    - get_count() : 이진트리의 노드의 수를 반환한다.
    - get_leaf_count() : 이진트리의 단말 노드의 수를 반환한다.
    = get_height() : 이진트리의 높이를 반환한다.

3. 구현

이진트리도 선형 자료형에서와 마찬가지로 배열을 이용해 표현하거나 링크를 이용한 연결된 표현 방법으로 나타낼 수 있다.

배열 표현법

이진트리가 완전 이진트리라고 가정하여 트리의 높이(k)에 따라 알맞는 크기($2^k-1$)의 배열을 생성하고, 완전 이진트리의 번호대로 노드들을 저장한다.

포화 이진트리나 완전 이진트리에는 적합하지만 일반적인 이진트리에서는 기억 공간의 낭비가 심할 수 있다.

어떤 노드의 인덱스$(i)$를 알면 그 노드의 부모와 자식의 인덱스를 계산할 수 있다.

  • Parent node index = i / 2
  • Left child node index = 2i
  • Right child node index = 2i + 1

링크 표현법

데이터를 저장하는 필드, 왼쪽 자식 노드를 가리키는 포인터 변수, 오른쪽 자식 노드를 가리키는 포인터 변수로 구성된 노드를 이용한다.

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

typedef int TElement;
typedef struct BinTrNode {
    TElement data; // 노드에 저장할 데이터
    struct BinTrNode* left; // 왼쪽 자식 노드의 포인터
    struct BinTrNode* right; // 오른쪽 자식 노드의 포인터
} TNode;

TNode* root; // root node의 포인터

이진 트리 초기화 함수

// 이진 트리 초기화하기
void init_tree() {root = NULL;}

이진 트리 공백 여부 확인 함수

// 공백 상태 확인하기
int is_empty_tree() {return root == NULL;}

이진 트리 생성 함수

// 이진트리 생성하기
TNode* create_tree(TElement val, TNode* l, TNode* r)
{
    TNode* n = (TNode*)malloc(sizeof(TNode));
    n -> data = val;
    n -> left = l;
    n -> right = r;
    return n;
}

이진 트리의 루트 노드 반환 함수

// 루트 노드 반환하기
TNode* get_root() {return root;}

이진 트리의 노드 개수 함수

// 노드 개수 구하기
int count_node(TNode *n)
{
    if(n == NULL) return 0;
    return 1 + count_node(n -> left) + count_node(n -> right);
}

이진 트리의 단말 노드 개수 함수

// 단말 노드 개수 구하기
int count_leaf(TNode *n) {
    if(n == NULL) return 0;
    if(n -> left == NULL && n -> right == NULL) return 1;
    else return count_leaf(n -> left) + count_leaf(n -> right);
}

이진 트리의 높이 함수

// 트리의 높이 구하기
int calc_height(TNode *n)
{
    int hLeft, hRight;
    if(n == NULL) return 0;
    hLeft = calc_height(n -> left);
    hRight = calc_height(n -> right);
    return (hLeft > hRight) ? hLeft + 1 : hRight + 1;
}

int main()
{
    TNode *a, *b, *c, *d, *e, *f, *g, *h, *i, *j;

    init_tree();
    g = create_tree(7, NULL, NULL);
    h = create_tree(8, NULL, NULL);
    i = create_tree(9, NULL, NULL);
    j = create_tree(10, NULL, NULL);
    f = create_tree(6, NULL, NULL);
    d = create_tree(4, g, h);
    e = create_tree(5, i, j);
    b = create_tree(2, d, e);
    c = create_tree(3, NULL, f);
    a = create_tree(1, b, c);

    printf("노드의 개수 = %d\n", count_node(a));
    printf("단말의 개수 = %d\n", count_leaf(a));
    printf("트리의 높이 = %d\n", calc_height(a));

    return 0;
}
// 출력 결과
// 노드의 개수 = 10
// 단말의 개수 = 5
// 트리의 높이 = 4

4. 이진트리의 순회

  • Traversal(순회) : 트리에 속하는 모든 노드를 한 번씩 방문하여 노드의 데이터를 목적에 맞게 처리하는 것

이진트리는 전체 트리와 서브 트리의 구조가 완전히 동일하다. 전체 트리 순회에 사용된 알고리즘을 서브 트리에 동일하게 적용할 수 있다.

  • Preorder traversal(전위 순회) : 루트(자기 자신) -> 왼쪽 서브트리 -> 오른쪽 서브트리
  • Inorder traversal(중위 순회) : 왼쪽 서브트리 -> 루트(자기 자신) -> 오른쪽 서브트리
  • Postorder traversal(후위 순회) : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트(자기 자신)
  • Level order(레벨 순회) : 각 노드를 레벨 순으로 검사하는 방법

순회 방법 순회 결과
전위 순회 A-B-D-H-I-E-J-K-C-F-G
중위 순회 H-D-I-B-J-E-K-A-F-C-G
후위 순회 H-I-D-J-K-E-B-F-C-G-A
레벨 순회 A-B-C-D-E-F-G-H-I-J-K 
#include <stdio.h>
#include <stdlib.h>

typedef int TElement;
typedef struct BinTrNode {
    TElement data; // 노드에 저장할 데이터
    struct BinTrNode* left; // 왼쪽 자식 노드의 포인터
    struct BinTrNode* right; // 오른쪽 자식 노드의 포인터
} TNode;

TNode* root; // root node의 포인터

void init_tree() {root = NULL;}
int is_empty_tree() {return root == NULL;}
TNode* get_root() {return root;}

TNode* create_tree(TElement val, TNode* l, TNode* r)
{
    TNode* n = (TNode*)malloc(sizeof(TNode));
    n -> data = val;
    n -> left = l;
    n -> right = r;
    return n;
}

전위 순회

// 전위 순회
void preorder(TNode *n)
{
    if (n != NULL) {
        printf("[%d]", n -> data);
        preorder((n -> left));
        preorder((n -> right));
    }
}

중위 순회

// 중위 순회
void inorder(TNode * n) {
    if (n != NULL) {
        inorder(n -> left);
        printf("[%d]", n -> data);
        inorder(n -> right);
    }
}

후위 순회

// 후위 순회
void postorder(TNode *n)
{
    if (n != NULL) {
        postorder(n -> left);
        postorder(n -> right);
        printf("[%d]", n -> data);
    }
}

레벨 순회

// 레벨 순회
#define MAX_QUEUE_SIZE 100
typedef TNode* Element;

Element data[MAX_QUEUE_SIZE];
int front;
int rear;

void error(char str[])
{
    printf("%s\n, str");
    exit(1);
}

void init_queue() {front = rear = 0;}
int is_empty() {return front == rear;};
int is_full() {return front==(rear + 1) % MAX_QUEUE_SIZE;}
int size() {return(rear - front + MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE;}

void enqueue(Element val)
{
    if(is_full()) error("큐 포화 에러");
    rear = (rear + 1) % MAX_QUEUE_SIZE;
    data[rear] = val;
}

Element dequeue()
{
    if (is_empty()) error("큐 공백 에러");
    front = (front + 1) % MAX_QUEUE_SIZE;
    return data[front];
}
Element peek()
{
    if(is_empty()) error("큐 공백 에러");
    return data[(front + 1) % MAX_QUEUE_SIZE];
}

void levelorder(TNode *root)
{
    TNode* n;

    if (root == NULL) return;
    init_queue();
    enqueue(root);
    while (!is_empty()) {
        n = dequeue();
        if (n != NULL) {
            printf("[%d]", n -> data);
            enqueue(n -> left);
            enqueue(n -> right);
        }
    }
}

int main()
{
    TNode *a, *b, *c, *d, *e, *f, *g, *h, *i, *j;

    init_tree();
    g = create_tree(7, NULL, NULL);
    h = create_tree(8, NULL, NULL);
    i = create_tree(9, NULL, NULL);
    j = create_tree(10, NULL, NULL);
    f = create_tree(6, NULL, NULL);
    d = create_tree(4, g, h);
    e = create_tree(5, i, j);
    b = create_tree(2, d, e);
    c = create_tree(3, NULL, f);
    a = create_tree(1, b, c);

    printf("\n   In-Order : "); inorder(a);
    printf("\n  Pre-Order : "); preorder(a);
    printf("\n Post-Order : "); postorder(a);
    printf("\nlevel-Order : "); levelorder(a);
    printf("\n");

    return 0;
}

// 출력 결과
//    In-Order : [7][4][8][2][9][5][10][1][3][6]
//   Pre-Order : [1][2][4][7][8][5][9][10][3][6]
//  Post-Order : [7][8][4][9][10][5][2][6][3][1]
// level-Order : [1][2][3][4][5][6][7][8][9][10]

You may also enjoy