트리에서 전위 중위 후위 순회 하는 방법은 각 순회의 특징을 그대로 적용하는 것이다.
전위는 현재 노드를 먼저 읽는 방식으로 현재노드 -> 좌 -> 우
중위는 좌측 노드부터 먼저 읽는 방식으로 좌 -> 현재노드 -> 우
후위는 자식들을 전부 읽고 자신을 읽는 방식으로 좌 -> 우 -> 현재노드
이를 코드로 표현하면 다음과 같다
|
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
|
struct tree {
int w;
tree* parent = NULL;
tree* left = NULL;
tree* right = NULL;
bool visit = false;
};
void pre(tree* now) { // 전위
if (now == NULL || now->visit) return;
now->visit = true;
cout << now->w << " ";
pre(now->left);
pre(now->right);
}
void in(tree* now) { // 중위
if (now == NULL || now->visit) return;
now->visit = true;
in(now->left);
cout << now->w << " ";
in(now->right);
}
void post(tree* now) { // 후위
if (now == NULL || now->visit) return;
now->visit = true;
post(now->left);
post(now->right);
cout << now->w << " ";
}
void solve() {
cout << "pre : ";
pre(root);
for (int i = 0; i < tree_size; i++) node[i].visit = false;
cout << "\n";
cout << "in : ";
in(root);
for (int i = 0; i < tree_size; i++) node[i].visit = false;
cout << "\n";
cout << "post : ";
post(root);
for (int i = 0; i < tree_size; i++) node[i].visit = false;
}
|
다음과 같은 결과를 얻을 수 있다.
pre : 5 3 1 0 2 4 7 6 8 10 9 12 11
in : 0 1 2 3 4 5 6 7 8 9 10 11 12
post : 0 2 1 4 3 6 9 11 12 10 8 7 5
'algorithm > algorithm' 카테고리의 다른 글
| 강한 결합 요소 SCC(Strong connected component) (0) | 2020.06.22 |
|---|---|
| 두 노드간의 최단or최장거리 찾기 (0) | 2020.04.27 |
| 전위, 중위 정보로 트리 만들기 (0) | 2020.04.24 |
| c,c++ 세 점이 주어졌을 때 각도 구하기 (0) | 2020.04.10 |
| STL 사용할때 주의할 것(set,map,...) (0) | 2020.04.10 |
