[알골90제] 58번 - 이진트리 깊이우선탐색(DFS)

 

- 이진트리 : 기본구성이 부모노드, 왼쪽 자식노드, 오른쪽 자식노드, 3개가 기본구성

- 가정:

부모노드에서 *2하면 왼쪽자식

부모노드에서 *2+1하면 오른쪽 자식

- 재귀함수로 탐색할 것임

- 깊이우선탐색이 무엇인가?

 : 출발된 노드에서 연결된 노드중에 아무거나 하나를 선택해서 방문하는 것임

그러다 더이상 갈곳이 없다면, 되돌아가서 가지 않았던 노드로 가는 것

 

전위순회: 부모노드 먼저 출력 -> 왼쪽 -> 오른쪽 자식 출력

중위순회: 부모노드를 중간에 출력하면 중위 순회. 루트노드를 언제 출력하나가 기준임.

왼쪽 자신 먼저 출력->부모노드->오른쪽자식 출력

후위순회 출력: 왼쪽 출력->오른쪽 출력-> 부모출력

 

코드 구현

 

- 57번에서 배운 재귀/스택과 유사!

- 9번 라인까지 기억되고 넘어감, 재귀가 다 끝나면 10번라인으로 가서 마저 처리해줌

- 트리를 호출하고 있는 구성만 하는 중

 

 

**후위 순회가 굉장히 중요!

병합정렬이 왼쪽 오른쪽 자식들이 다 일을 끝내고나서 자기 일을 하는, 후위 순회를 사용함

 

- 전위순회 : 기본형

=> 자기 함수의 할일을 먼저 하고 가지를 뻗어 나가는 것

 

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

void D(int v) {
	if (v > 7) return;
	else {
		printf("%d", v);
		D(v * 2);
		D(v * 2 + 1);
	}
}

int main() {
	
	D(1);
	return 0;

}

출력: 1245367

 

 

- 중위순회 : 왼쪽 자식이 할일 끝내면 부모인 내것 하는것

 

//58번 이진트리 깊이우선탐색 DFS: Depth First Search


#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

void D(int v) {
	if (v > 7) return;
	else {
		//printf("%d", v); //전위순회
		D(v * 2);
		printf("%d", v); //중위순회
		D(v * 2 + 1);
	}
}

int main() {
	
	D(1);
	return 0;

}

 

 

- 후위순회: 자식들 다 끝내고 하는 것

 

//58번 이진트리 깊이우선탐색 DFS: Depth First Search


#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;

void D(int v) {
	if (v > 7) return;
	else {
		//printf("%d", v); //전위순회
		D(v * 2);
		//printf("%d", v); //중위순회
		D(v * 2 + 1);
		printf("%d", v); //후위순회

	}
}

int main() {
	
	D(1);
	return 0;

}

 

 

 

후위순회가 도는 과정 - 스택

함수는 자기일을 다 끝내면 스택을 빠져나옴