[c++] 이진트리 깊이우선탐색(DFS)과 재귀함수

깊이우선탐색은 루트 노드가 어디에 위치하는가에 따라서 세가지로 나뉘어 진다.

 

전위순회, 중위순회, 후위순회

전위순회

• 루트노드가 가장 먼저 나오는 방식
• 루트노드가 가장 먼저 나오고나서 왼쪽부터 노드들을 순회

중위순회

• 루트노드가 중간에 나오는 방식
• 노드들의 왼쪽부터 순회하여 루트노드가 중간에 나옴

후위순회

• 루트노드가 마지막에 나오는 방식
• 왼쪽노드 -> 오른쪽노드 -> 부모노드 순서로 순회

 

각각의 예제코드

아래는 트리를 구성하는 코드이다.

#include <iostream>
using namespace std;
void D(int v){
	if(v>7) return;
	else {
		D(v*2);
		D(v*2+1);
	}
}
int main() {
	D(1);
	return 0;
}

위 코드에서는 D라는 재귀함수를 계속적으로 호출하고 있지만

D에서 처리하는 일은 명시되어 있지 않다.

D(v*2)는 왼쪽 노드를 뜻하며 D(v*2+1)은 오른쪽 노드를 뜻한다.

 

전위순회 코드

#include <iostream>
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;
}

위 코드를 실행한 결과는 1 2 4 5 3 6 7이다.

재귀함수가 호출되기 전에 일처리가 이루어지므로 루트노드부터 출력된다.

(여기에서 일처리란 printf로 입력된 숫자가 출력되는 것을 뜻한다.)

 

중위순회 코드

#include <iostream>
using namespace std;
void D(int v){
	if(v>7) return;
	else {	
		D(v*2);
        	printf("%d ", v);
		D(v*2+1);
	}
}
int main() {
	D(1);
	return 0;
}

전위순회코드에서 변경된 것은 왼쪽노드와 오른쪽노드 사이에서 일을 처리한다는 것이다.

따라서 루트노드가 중간에 출력될 수 밖에 없다.

위 코드를 실행한 결과는 4 2 5 1 6 3 7 이다.

 

후위순회 코드

#include <iostream>
using namespace std;
void D(int v){
	if(v>7) return;
	else {	
		D(v*2);
		D(v*2+1);
        	printf("%d ", v);
	}
}
int main() {
	D(1);
	return 0;
}

마찬가지로 변경된 것은 일처리하는 코드의 위치밖에 없다.

하지만 결과는 4 5 2 6 7 3 1로 루트노드가 마지막에 나오는 것을 볼 수 있다.

 

당연하게 printf에 위치에 따라 출력순서가 달라지는 것은 알겠지만 정확히 그 과정이 궁금해서 

후위순회만 그림으로 그려서 과정을 살펴보았다.

 

후위 순회의 경우 stack 자료구조에 어떻게 들어갈까?

앞서 말했듯이 후위순회는 printf가 왼쪽과 오른쪽노드를 출력하는 재귀함수보다 뒤에 선언되어 있다.

위 그림은 스텍 자료구조에 D함수가 처리되는 과정을 그린 것이며

D함수의 옆에 파란색은 복귀주소값(여기에서는 편의상 돌아갈 코드의 행을 뜻함)을 적어 둔 것이고

빨간색은 함수가 출력하는 숫자를 의미한다.

만약 D(1) 8 이라면 D(1)함수가 다른 재귀함수의 처리를 끝내고 돌아왔을 때 8행부터 다시 시작하겠다라는 의미이다.

 

왼쪽부터 1번으로 지정하면

1 - 스텍에 아무것도 없음

2 - D(1) 함수가 호출되고 일처리를 하다보니 처리해야할 재귀함수 D(2)를 만남

3 - D(2) 함수가 호출되고 일처리를 하다보니 처리해야할 재귀함수 D(4)를 만남

4 - D(2) 함수가 호출되고 일처리를 하다보니 처리해야할 재귀함수 D(8)를 만남

5 - 

 (1) D(8)이 호출되어서 일처리를 하다보니 v>7 인 경우에 해당하여 return됨 

 (2) return 된 후 D(4)는 다음줄 처리

 (3) D(9)이 호출되어서 일처리를 하다보니 v>7 인 경우에 해당하여 return됨 

 (4) return 된 후 D(4)는 다음줄 처리하면서 printf를 만나 4가 출력됨

6 - D(2) 함수로 돌아와서 일처리를 하다보니 D(5)를 만남 

7 - 

 (1) D(10)이 호출되어서 일처리를 하다보니 v>7 인 경우에 해당하여 return됨 

 (2) return 된 후 D(5)는 다음줄 처리

 (3) D(11)이 호출되어서 일처리를 하다보니 v>7 인 경우에 해당하여 return됨 

 (4) return 된 후 D(5)는 다음줄 처리하면서 printf를 만나 5가 출력됨

8 - D(2) 함수로 돌아와서 printf를 만나 2가 출력됨

 

이와 같은 형식으로 계속 진행하면 아래 그림과 같이 진행이 된다.

그래서 결국에는 6 7 3 1 순으로 출력이 되며 

4 5 2 6 7 3 1 이라는 결과가 도출된다.

 

예전에 재귀함수에 대해서 배운게 기억이 났는데 어떤 자료구조에 들어가며 어떤순서로 함수가 동작하는지 주의깊게 보지 않았던 것 같다.그래서 굉장히 어려웠고 약간은 놓아 버렸던 기억이 있다..^^

 

어떤 알고리즘이 어떤 자료구조를 통해 구현되는지 알고 코드를 다시보니 

조금은 이해가 쉬운 것 같다. 

 

 

본 포스팅은 인프런 it 취업을 위한 알고리즘 문제풀이(with C/C++) 강의를 보고 작성하였습니다.

잘못된 부분이 있다면 답글달아주세요:)

트it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비ㅇㅇㅇ어it 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비it 취업을 위한 알고리즘 문제풀이 (wit 취업을 위한 알고리즘 문제풀이 (with C/C++) : 코딩테스트 대비ith C/C++) : 코딩테스트 대비