반응형

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



이 문제는 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


반응형