자료구조/DFS
트리 (Tree)
트리 (Tree)란 노드들이 나무 가지처럼 연결된 비선형 계층적 자료구조입니다. 트리는 다음과 같이 나무를 거꾸로 뒤집어 놓은 모양과 유사합니다.
컴퓨터의 direcory구조가 트리 구조의 대표적인 예가 될 수 있습니다.
트리 구조에서 사용되는 기본 용어
노드 (Node)
트리를 구성하고 있는 기본 요소
노드에는 키 또는 값과 하위 노드에 대한 포인터를 가지고 있음.
A, B, C, D, E, F, G, H, I, J
간선 (Edge)
노드와 노드 간의 연결선
루트 노드 (Root Node)
트리 구조에서 부모가 없는 최상위 노드
root node : A
부모 노드 (Parent Node)
자식 노드를 가진 노드
H, I에 부모 노드는 D
자식 노드 (Child node)
부모 노드의 하위 노드
노드 D의 자식 노드는 H, I
형제 노드 (Sibling node)
같은 부모를 가지는 노드
H, I는 같은 부모를 가지는 형제 노드
외부 노드(external node, outer node), 단말 노드 (terminal node), 리프 노드(leaf node)
자식 노드가 없는 노드
H, I, J, F, G
내부 노드 (internal node, inner node), 비 단말 노드 (non-terminal node), 가지 노드 (branch node)
자식 노드 하나 이상 가진 노드
A, B, C, D, E
깊이 (depth)
루트에서 어떤 노드까지의 간선(Edge) 수
루트 노드의 깊이 : 0
D의 깊이 : 2
높이 (height)
어떤 노드에서 리프 노드까지 가장 긴 경로의 간선(Edge) 수
리프 노드의 높이 : 0
A 노드의 높이 : 3
트리 종류
편향 트리 (skew tree) 모든 노드들이 자식을 하나만 가진 트리 왼쪽 방향으로 자식을 하나씩만 가질 때 left skew tree, 오른쪽 방향으로 하나씩만 가질 때 right skew tree라고 함.
이진트리 (Binary Tree) 각 노드의 차수(자식 노드)가 2 이하인 트리 이진 탐색 트리 (Binary Search Tree, BST) 순서화된 이진 트리 노드의 왼쪽 자식은 부모의 값보다 작은 값을 가져야 하며 노드의 오른쪽 자식은 부모의 값보다 큰 값을 가져야 함. m 원 탐색 트리(m-way search tree) 최대 m개의 서브 트리를 갖는 탐색 트리 이진 탐색 트리의 확장된 형태로 높이를 줄이기 위해 사용함. 균형 트리 (Balanced Tree, B-Tree) m원 탐색 트리에서 높이 균형을 유지하는 트리 height-balanced m-way tree라고도 함.
트리 하드코딩 하기
인접행렬로 표현하는 경우
1
2
3
4
5
6
7
8
9
10
char value[5] = { 'D','E','F','Q','A' };
int matrix[5][5] =
{
0,1,1,1,0,
0,0,0,0,1,
0,0,0,0,0,
0,0,0,0,0,
0,0,0,0,0,
};
리스트로 표현 하는 경우
1차원 배열로 표현하는 경우
char map[256] = “ ERWG RW K”;
rootNode를 1번으로 왼쪽자식은 부모 index * 2 오른쪽 자식은 부모 index *2 + 1
자식노드 출력해보기
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
#include<iostream>
int main()
{
char value[10] = "DEFQZVM";
int map[7][7] =
{
0,1,1,1,0,0,0,
0,0,0,0,1,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,1,1,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
0,0,0,0,0,0,0,
};
int n = 0;
std::cin >> n;
for (size_t i = 0; i < 7; i++)
{
if (map[n][i] > 0)
{
std::cout << value[i] << std::endl;
}
}
return 0;
}
부모 노드 출력 해보기
1
2
3
4
5
6
7
8
9
10
11
12
13
#include<iostream>
int main()
{
char map[15] = " ERWG RW K ";
int n = 0;
std::cin >> n;
std::cout << map[n / 2] << std::endl;
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
DFS
재귀호출,스택을 사용하여 노드를 탐색한다. Depth First Search(깊이 우선 탐색)
노드를 깊숙히 안쪽으로 들어가면서 탐색한다.
트리,그래프 둘다 연습해야한다.
BFS
큐를 이용하여 , 노드를 탐색한다. Breadth First Search(너비 우선 탐색)
노드의 레벨 또는 너비를 우선적으로 탐색한다.
트리,그래프 둘다 연습해야한다.
트리냐 그래프냐에 따라서 큰 순회방법은 비슷하지만
특정조건이 들어갈수 있기때문에 구현방법이 달라질수 있다.
트리 순회 (dfs)
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
char value[6] = "TBECD";
char path[6] = "";
int map[5][5] =
{
0,1,1,0,0,
0,0,0,1,1,
0,0,0,0,0,
0,0,0,0,0,
0,0,0,0,0,
};
void run(int now, int level)
{
std::cout << value[now];
for (size_t i = 0; i < 5; i++)
{
if (map[now][i] == 1)
{
path[level + 1] = value[i];
run(i, level + 1);
path[level + 1] = 0;
}
}
}
int main()
{
path[0] = 'T';
run(0, 0);
return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
char map1D[7] = " TBECD";
void run1D(int now)
{
if (now >= 7 || map1D[now] == ' ')
{
return;
}
std::cout << map1D[now];
run1D(now * 2);
run1D(now * 2 + 1);
}
int main()
{
run1D(1);
return 0;
}
그래프 순회 (dfs)
그래프 순회는 트리순회에서 중복 방문 여부만 체크해주면 된다.
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
#include <iostream>
char value[6] = "TEQWA";
char path[6] = "";
int visited[5] = {};
int map[5][5] =
{
0,1,0,0,0,
0,0,1,1,0,
0,0,0,0,0,
1,0,0,0,1,
0,0,0,0,0,
};
void run(int now, int level)
{
std::cout << value[now];
for (size_t i = 0; i < 5; i++)
{
if (map[now][i] == 1
&& visited[i] == 0)
{
path[level + 1] = value[i];
visited[i] = 1;
run(i, level + 1);
path[level + 1] = 0;
}
}
}
int main()
{
path[0] = 'T';
visited[0] = 1;
run(0, 0);
return 0;
}