+) 이진트리 깊이우선탐색 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); //해당 주석을 풀면, 전위순회 출력 : 1 2 4 5 3 6 7
        D(v*2);
        //printf("%d", v); //해당 주석을 풀면, 중위순회 출력 : 4 2 5 1 6 3 7
        D(v*2+1);
        //printf("%d", v); //해당 주석을 풀면, 후위순회 출력 : 4 5 2 6 7 3 1
    }
}

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

일단 어떤 개념인지 파악하고, 자세한 부분은 문제를 풀면서 익혀보자

(참고 : IT 취업을 위한 알고리즘 문제풀이 (with C/C++))