58. 이진트리 깊이우선탐색(DFS) (it 취업을 위한 알고리즘 문제풀이 입문 (with C/C++) : 코딩테스트 대비) ★★★★★

#include <stdio.h>


void D(int x)
{
	if(x < 8)
	{
		//printf("%d", x); 전위순회 
		D(x*2);
		//printf("%d", x); 중위순회 
		D(x*2+1);
		printf("%d", x);
	}
}


int main()
{
	int n;
	scanf("%d", &n);
	
	D(n);
	
	return 0;
}

1. 이진트리 깊이우선탐색(DFS) 는 부모노드, 좌/우 자식노드를 기본 구성으로 하는 이진트리를 이용한 탐색방법으로, 미로를 한 방향으로 길이 없을 때까지 갔다가 길이 막히면 다시 최근 갈림길로 돌아와 다른 방향으로 진행하는 느낌과 같다.

2. 전위순회는 부모노드 출력, 왼쪽 자식노드 출력, 오른쪽 자식노드 출력 순이다.

3. 중위순회는 왼쪽 자식노드 출력, 부모노드 출력, 오른쪽 자식노드 출력 순이다.

4. 후위순회는 좌/우 자식노드 출력, 부모노드 출력 순이다. 이 방식은 나중에 병합정렬에도 사용된다.(가장 작은 단위의 일을 처리하고 큰 일을 처리하는 방식)