Programming/C++
[C++] DFS 깊이우선탐색
100winone
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
후위 순회
후위 순회는 루트노드가 가장 마지막에 출력된다
순서는 왼쪽 노드 오른쪽 노드 부모 노드 순으로 간다.
순서 : 4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
/*dfs의 기본형*/
/*dfs는 기본적으로 전위순회를 쓸 것*/
void recur(int v) {
if (v > 7) return;
else {
/*이진트리 함수를 뻗어감*/
printf("%d ", v); // 전위 순회
recur(v * 2);
// printf("%d ", v); // 중위 순회
recur(v * 2 + 1);
// printf("%d ", v); // 후위 순회
}
}
int main() {
recur(1); // 부모노드
return 0;
}