Tree
개요
트리순회
트리 순회는 2진트리에서 트리를 순회하는 것을 말한다.
총 4가지의 순회 알고리즘이 있고, 각각의 알고리즘을 알아보고자 한다.
- 후위순회(postorder traversal)
- 전위순회(preorder traversal)
- 중위순회(inorder traversal)
- 레벨순회(level traversal)
후위순회
후위순회(postorder traversal)는 자식들 노드를 방문하고 자신의 노드를 방문하는 것
수도코드
1
2
3
4
5
6
7
8
postorder( node )
// 방문하지 않았더라면
if (node.visited == false)
// 왼쪽 노드(자식노드) 방문
postorder( node->left )
postorder( node->right )
// 오른쪽 노드(본인노드) 방문
node.visited = true
전위순회
전위순회(preorder traversal)는 먼저 자신의 노드를 방문하고 그 다음 노드들을 방문하는 것
수도코드
1
2
3
4
5
6
7
8
9
postorder( node )
// 방문하지 않았더라면
if (node.visited == false)
// 오른쪽 노드(본인노드) 방문
node.visited = true
postorder( node-> right)
// 왼쪽 노드(자식노드) 방문
postorder( node->left )
중위순회
중위순회(inorder traversal)는 왼쪽 노드를 먼저 방문 그다음의 자신의 노드를 방문하고 그 다음 오른쪽 노드를 방문하는 것
수도코드
1
2
3
4
5
inorder( node )
if (node.visited == false)
inorder( node->left )
node.visited = true
inorder( node->right )
레벨순회
레벨순회(level traversal) BFS(너비우선 탐색)를 생각하면 된다.
Q. 아래의 그래프가 주어졌을 때 preorder, inorder, postorder를 구현하라.
수도코드를 보고 코드를 구축하는 연습을 하셔야 합니다. 아래와 같이 그래프가 주어졌을 때 비어진 함수를 채워서 preorder, inorder, postorder를 구현하고 이 때 방문했을 때 해당 노드를 출력하는 것을 구현하라.
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
#include <iostream>
#include <vector>
using namespace std;
vector<int> adj[1004];
int visited[1004];
// 전위순회
void postOrder(int here){
}
// 후위순회
void preOrder(int here){
}
// 중위순회
void inOrder(int here){
}
int main(){
/*
1
2 3
4 5
*/
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
int root = 1;
cout << "\n 트리순회 : postOrder \n";
postOrder(root); memset(visited, 0, sizeof(visited));
cout << "\n 트리순회 : preOrder \n";
preOrder(root); memset(visited, 0, sizeof(visited));
cout << "\n 트리순회 : inOrder \n";
inOrder(root);
return 0;
}
정답코드
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
#include <bits/stdc++.h>
using namespace std;
vector<int> adj[1004];
int visited[1004];
void postOrder(int here){
if(visited[here] == 0){
if(adj[here].size() == 1)postOrder(adj[here][0]);
if(adj[here].size() == 2){
postOrder(adj[here][0]);
postOrder(adj[here][1]);
}
visited[here] = 1;
cout << here << ' ';
}
}
void preOrder(int here){
if(visited[here] == 0){
visited[here] = 1;
cout << here << ' ';
if(adj[here].size() == 1)preOrder(adj[here][0]);
if(adj[here].size() == 2){
preOrder(adj[here][0]);
preOrder(adj[here][1]);
}
}
}
void inOrder(int here){
if(visited[here] == 0){
if(adj[here].size() == 1){
inOrder(adj[here][0]);
visited[here] = 1;
cout << here << ' ';
}else if(adj[here].size() == 2){
inOrder(adj[here][0]);
visited[here] = 1;
cout << here << ' ';
inOrder(adj[here][1]);
}else{
visited[here] = 1;
cout << here << ' ';
}
}
}
int main(){
adj[1].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
adj[2].push_back(5);
/*
1
2 3
4 5
*/
int root = 1;
cout << "\n 트리순회 : postOrder \n";
postOrder(root); memset(visited, 0, sizeof(visited));
cout << "\n 트리순회 : preOrder \n";
preOrder(root); memset(visited, 0, sizeof(visited));
cout << "\n 트리순회 : inOrder \n";
inOrder(root);
return 0;
}
/*
트리순회 : postOrder
4 5 2 3 1
트리순회 : preOrder
1 2 4 5 3
트리순회 : inOrder
4 2 5 1 3
*/