트리

트리는 비선형 자료구조로 노드로 구성되어 있습니다. 노드들이 링크(선)를 통해 연결되어 있으며 계층적 구조를 나타내고자 할때 사용됩니다.


아래의 트리 그림을 가지고 하나하나 기본적인 설명을 하도록 하겠습니다.






⊙루트노드 (root) : 트리의 가장 위, 즉 최상위 노드를 말합니다. 트리에서 가장 중요한 노드입니다. 여기서 A가 루트노드입니다.




잎 또는 단말 노드 (leaf) : 트리의 가장 끝자락에 위치한 노드입니다. 위 트리에서는 G, H, E, I, J가 해당됩니다.


부모노드 (parent) : 현재노드의 한단계 위 계층에 있는 노드를 말합니다. I의 부모노드는 F, C의 부모노드는 A입니다. 


형제노드 (sibling) : 부모가 같은 노드를 의미합니다. D의 형제노드는 E, G의 형제노드는 H입니다.


내부노드 (internal) : leaf가 아닌 노드를 의미합니다.

노드 깊이 (depth) : 루트에서 시작해서 얼마나 깊이 들어가야 그 노드를 만날 수 있는지를 깊이라고 합니다. 기준이 루트노드이므로 A의 깊이는 0, C의 깊이는 1, H의 깊이는 3입니다.

노드 레벨 (level) : 같은 깊이를 갖는 노드의 집합입니다. 단, 깊이와는 다르게 1부터 시작합니다. 레벨 1의 노드는 A, 레벨 2의 노드들은 B, C, 레벨 3의 노드들은 D, E, F가 되겠죠.

트리 높이 (height) : 가장 긴 깊이를 의미합니다. 위 트리의 높이는 3이 됩니다. 트리 높이는 트리에서 가장 중요한 요소인데, 노드의 갯수만큼 높이가 커지면 linkedlist와 성능이 같게 되죠. 그래서 높이가 트리에서 성능을 좌우합니다.

노드 차수 (degree) : 각 노드에서 나가는 선을 의미합니다. 즉, 가지수를 말하겠죠? A의 차수는 2, C의 차수는 1이 됩니다.

트리의 차수 :  가장 큰 차수를 갖고 있는 노드의 차수가 됩니다. 위의 트리에서는 2보다 큰 차수는 없으니, 트리의 차수는 2가 됩니다.

트리의 노드가 N이라고 할때 가지수는 무조건 N-1이 됩니다. 왜냐면 트리에서는 사이클이 존재하지 않기 때문인데, 위 트리에서 노드와 노드사이에 선을 한개만 더 추가하게 되면 사이클이 발생합니다. 특정 노드와 노드사이를 계속 돌 수 있다는 이야기죠. 그러니, 사이클이 발생하는 트리는 없습니다.


트리 순회


트리에는 크게 세가지의 순회 방법이 있습니다. 그 노드를 어떤 순서로 방문하느냐에 따라서 달라집니다. 그 전에 트리를 구현하는 방법을 알아보아야겠죠?


노드가 어떤 식으로 구성되어 있는 지 잠깐만 살펴보겠습니다.

1
2
3
4
5
typedef struct node {
    char data;
    struct node *left;
    struct node *right;
} Node;



각 노드는 data라는 변수를 갖고 있습니다. 이 data의 변수는 위 그림에서 알파벳을 저정하고 있습니다.

그리고 left는 그 노드의 왼쪽 자식 노드, right는 그 노드의 오른쪽 자식노드를 의미합니다. 가장 끝에 있는 노드는 left와 right가 NULL이라는 점입니다.


위 트리를 3가지 순회방법인 전위순회, 후위순회, 중위순회 순으로 탐색해봅시다




전위순회(preorder traversal)

전위순회는 현재 노드를 가장 먼저 방문합니다. 그러니 왼쪽 자식과 오른쪽 자식을 현재 자식보다 나중에 방문합니다.

위 그래프를 전위순회로 방문하게 된다면 

A -> B -> D -> G -> H -> E -> C ->F ->I -> J

순으로 트리가 방문됩니다.

1
2
3
4
5
6
void preorder(Node *node) {
    if (node == NULL) return;
    printf(" %c ", node->data);
    preorder(node->left);
    preorder(node->right);
}



후위순회(postorder traversal)

이름에서부터 짐작하셨겠지만 현재 노드를 가장 나중에 방문하는 방식의 순회입니다. 그러니 왼쪽 자식, 오른쪽 자식 노드를 우선적으로 방문합니다.

그러니 후위순회의 결과는

G -> H -> D -> E -> B ->I -> J -> F -> C -> A

입니다.

1
2
3
4
5
6
void postorder(Node *node) {
    if (node == NULL) return;
    postorder(node->left);
    postorder(node->right);
    printf(" %c ", node->data);
}



중위순회(inorder traversal)

우선 왼쪽 자식을 방문하고, 현재 노드를 방문합니다. 그리고 나서 오른쪽 자식 노드를 방문하게 됩니다. 현재 노드를 중간에 방문한다고 해서 중위순회가 됩니다.

방문 순서는 이렇습니다.

G -> D -> H -> B -> E -> A -> C ->I -> F -> J


1
2
3
4
5
6
void inorder(Node *node) {
    if (node == NULL) return;
    inorder(node->left);
    printf(" %c ", node->data);
    inorder(node->right);
}




전체코드

전체코드는 아래와 같습니다. 위의 트리를 그대로 코드로 옮긴거죠. 입력받으면서 동적으로 할 수도 있겠지만 그런 귀찮은 부분까지는 고려하지 않았습니다. 여러분들이 더 잘하실테니까요.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
    char data;
    struct node *left;
    struct node *right;
} Node;
 
Node *createNode(char data) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}
void preorder(Node *node) {
    if (node == NULL) return;
    printf(" %c ", node->data);
    preorder(node->left);
    preorder(node->right);
}
 
void postorder(Node *node) {
    if (node == NULL) return;
    postorder(node->left);
    postorder(node->right);
    printf(" %c ", node->data);
}
 
void inorder(Node *node) {
    if (node == NULL) return;
    inorder(node->left);
    printf(" %c ", node->data);
    inorder(node->right);
}
 
 
int main() {
    Node *A = createNode('A');
    Node *B = createNode('B');
    Node *C = createNode('C');
    Node *D = createNode('D');
    Node *E = createNode('E');
    Node *F = createNode('F');
    Node *G = createNode('G');
    Node *H = createNode('H');
    Node *I = createNode('I');
    Node *J = createNode('J');
    A->left = B;
    A->right = C;
    B->left = D;
    B->right = E;
    D->left = G;
    D->right = H;
    C->right = F;
    F->left = I;
    F->right = J;
 
 
    printf("전위 순회: ");
    preorder(A);
    printf("\n");
 
    printf("후위 순회: ");
    postorder(A);
    printf("\n");
 
    printf("중위 순회: ");
    inorder(A);
    printf("\n");
 
    return 0;
}


반응형
블로그 이미지

REAKWON

와나진짜

,