#C++#cpp#전위순회#중위순회#후위순회#dfs#깊이우선탐색#알고리즘#코딩#코딩테스트#코테
-
[C++] DFS 깊이우선탐색Programming/C++ 2020. 1. 5. 01:21
깊이우선탐색(DFS)은 기본적으로 모든 노드를 탐색하는 데 루트(root) 노드가 어디에 위치하느냐에 따라 전위 중위 후위로 나누어진다. 이 그림을 기준으로 가장 위에 1번이 루트노드가 되고, 그 아래 2번과 3번은 왼쪽 자식 오른쪽 자식이다. 왼쪽 자식은 (루트노드 * 2) 이고 오른쪽 자식은 (루트노드 * 2 + 1) 로 번호가 지정된다. 전위 순회 전위 순회는 루트노드가 가장 먼저 나오는 순회 방식이다. 기본적으로 DFS는 전위 순회를 가장 많이 사용한다. 순서 : 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7 중위 순회 중위 순회는 각 루트노드가 자식노드의 사이에 위치한다. 순서 : 4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7 후위 순회 후위 순회는 루트노드가 가장 마지막에..