×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,238,771명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형

아래 문제를 통해 배열 이진 트리를 이해 해보자.



이 문제는 2번 예시 때문에 포인터를 이용한 트리를 제작하기가 까다롭다.

왜냐하면 루트 노드를 알 수 없고 최종적으로 input을 다 받았을 때 알아 낼 수 있기 때문이다.



배열을 이용한 이진 트리의 제작의 핵심은 다음과 같다.


1
2
3
4
5
6
7
8
9
10
11
12
13
#define nodeNum 100002
 
typedef struct _tree {
    int left;
    int right;
    int chk;
    int parent;
}Tree;
 
Tree tree[nodeNum];
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


 

구조체를 보면 

int left, int right, int chk, int parent가 존재한다.


각각 용도는 다음과 같다.


left :: 왼쪽 자식 노드의 배열 번호를 가지고 있는다.


right :: 오른쪽 자식 노드의 배열 번호를 가지고 있는다.


chk :: 이 노드가 생성된 노드인지 확인한다.(-1이면 없는 노드, 1이면 있는 노드)


parent :: 이 노드의 부모 노드가 무엇인지 확인한다.(-1이면 루트 노드, 그외 숫자가 들어가 있다면 부모 노드가 존재)


이 구조체를 노드의 개수(혹은 + 1)만큼 선언해준다.


즉, 노드 번호가 1~12번까지 있었다면 nodeNum은 13이면 된다.


노드 번호가 1번 부터이니 배열 번호의 0번 배열은 이용할 수 없게 되니 13개를 선언해야한다. 



1
2
3
4
5
6
7
8
9
10
    for (int i = 0; i < nodeNum-1; i++)
    {
        tree[i].chk = -1;
        tree[i].right = -1;
        tree[i].left = -1;
        tree[i].parent = -1;
    }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


초기화를 통해 -1의 의미가 어떤 동작을 하는지 이해한다.


chk가 -1이면 없는 노드


left가 -1이면 왼쪽 자식이 없는 부모 노드


right가 -1이면 오른쪽 자식이 없는 부모 노드


parent가 -1이면 루트 노드가 될 수 있음을 암시






1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
    for (int i = 0; i < n-1; i++)
    {
        scanf("%d %d %d"&parent, &child, &pos);
 
        if (pos == 0)
        {
            tree[parent].left = child; // 부모 배열번호에 left값에 자식 배열번호 값을 넣는다.
            tree[parent].chk = 1// 부모 및 자식노드는 존재함을 선언
            tree[child].chk = 1;
            tree[child].parent = parent; // 자식의 부모를 알게해준다.
        }
 
        else
        {
            tree[parent].right = child; // 부모 배열번호에 right값에 자식 배열번호 값을 넣는다.
            tree[parent].chk = 1// 부모 및 자식노드는 존재함을 선언
            tree[child].chk = 1;
            tree[child].parent = parent; // 자식의 부모를 알게해준다.
        }
    }
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


tree[parent].left = child :: 부모 노드 번호의 왼쪽에 자식 번호를 넣어준다.


tree[parent].chk = 1 :: 부모 노드는 활성화 되어있다.


tree[child].chk = 1 :: 자식 노드는 활성화 되어있다.


tree[child].parent = parent :: 자식 노드가 부모 노드가 무엇인지 알게해준다.






위의 문제에 대한 소스 코드이자, 배열을 이용한 이진 트리의 내용이다.


이 코드를 이용, 응용하여 이진 트리를 다르게 꾸밀 수 도있다.


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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
// 배열을 이용한 이진 트리
 
#include <stdio.h>
#define nodeNum 100002
 
typedef struct _tree {
    int left;
    int right;
    int chk;
    int parent;
}Tree;
 
 
// 노드 개수만큼 배열 선언
Tree tree[nodeNum];
 
int k; // k번째 노드 찾기
 
int flag = 0// flag = 1이되면 순회를 마친다는 의미입니다.
 
void PreorderTraverse(int now)
{
    if (now == -|| tree[now].chk == -|| flag == 1)
        return;
 
//    printf("현재 노드 :: %d\n", now);
    k--;
    if (k == 0)
    {
        printf("%d", now);
        flag = 1;
    }
 
    PreorderTraverse(tree[now].left);
    PreorderTraverse(tree[now].right);
 
}
 
 
void InorderTraverse(int now)
{
    if (now == -|| tree[now].chk == -|| flag == 1)
        return;
 
    InorderTraverse(tree[now].left);
 
//    printf("현재 노드 :: %d\n", now);
    k--;
    if (k == 0)
    {
        printf("%d", now);
        flag = 1;
    }
 
    InorderTraverse(tree[now].right);
 
}
 
 
void PostorderTraverse(int now)
{
    if (now == -|| tree[now].chk == -|| flag == 1)
        return;
 
 
    PostorderTraverse(tree[now].left);
    PostorderTraverse(tree[now].right);
 
//    printf("현재 노드 :: %d\n", now);
    k--;
    if (k == 0)
    {
        printf("%d", now);
        flag = 1;
    }
}
 
int main()
{
    // 초기화 (1부터 시작일수도있으니 100001개를 초기화합니다.)
    for (int i = 0; i < nodeNum - 1; i++)
    {
        tree[i].chk = -1;
        tree[i].right = -1;
        tree[i].left = -1;
        tree[i].parent = -1;
    }
 
    int n;
    int parent, child, pos; // pos = 0 :: left, pos = 1 :: right
 
    scanf("%d"&n);
 
    for (int i = 0; i < n-1; i++)
    {
        scanf("%d %d %d"&parent, &child, &pos);
 
        if (pos == 0)
        {
            tree[parent].left = child; // 부모 배열번호에 left값에 자식 배열번호 값을 넣는다.
            tree[parent].chk = 1// 부모 및 자식노드는 존재함을 선언
            tree[child].chk = 1;
            tree[child].parent = parent; // 자식의 부모를 알게해준다.
        }
 
        else
        {
            tree[parent].right = child; // 부모 배열번호에 right값에 자식 배열번호 값을 넣는다.
            tree[parent].chk = 1// 부모 및 자식노드는 존재함을 선언
            tree[child].chk = 1;
            tree[child].parent = parent; // 자식의 부모를 알게해준다.
        }
    }
 
    int h; // h = 1 :: 전위 , h = 2 :: 중위 , h = 3 :: 후위 
    int now;
    scanf("%d %d"&h, &k);
 
    // 루트노드 찾기(현재 루트노드가 뭔지 모르니 찾아내야 합니다.)
    for (int i = 1; i < n ; i++)
    {
        // 아래 printf로 검증해보세요.
        //printf("node :: %d parent :: %d lchild :: %d rchild :: %d\n", i, tree[i].parent, tree[i].left, tree[i].right);
        if (tree[i].parent == -1)
            now = i;
    }
 
    // printf("루트 노드 :: %d\n", now); // 루트 노드 확인
 
    if (h == 1)
        PreorderTraverse(now);
    
    else if (h == 2)
        InorderTraverse(now);
 
    else if (h == 3)
        PostorderTraverse(now);
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형