[C++] DFS 깊이우선탐색

깊이우선탐색(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;
}