[Algorithm] 이진트리 깊이우선탐색(DFS)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 우선 이진트리란 모든 노드들의 자식 노드가 두 개 이하인 트리를 의미한다.

     이진트리를 배열에 담았을 때, 

     왼쪽 자식 노드로 가기 위해서는 부모 노드 index * 2 를 해주면 되고

     오른쪽 자식 노드로 가기 위해서는 부모 노드 index * 2 + 1 을 해주면 된다.

    전위, 중위, 후위 순회는 그래프의 순회 순서를 의미하는데

    부모노드 기준(전위, 중위, 후위)으로 이루어 진다.

    전위 순회는 부모 노드를 먼저,

    중위 순회는 부모 노드를 중간에

    후위 순회는 부모 노드를 마지막에 방문하게 된다.

#. Code

0. 기본 DFS 호출 코드

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;    
 
void D(int x){
    if(x>7) return;
    else{
        D(x*2);
        D(x*2+1);
    }
}    
 
int main(){
    freopen("input.txt", "rt", stdin);
    D(1);
    return 0;
}

1. 전위 순회

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;    
 
void D(int x){
    if(x>7) return;
    else{
        printf("%d ", x);
        D(x*2);
        D(x*2+1);
    }
}    
 
int main(){
    D(1);
    return 0;
}

왼쪽 자식 호출 line 11 과 오른쪽 자식 호출 line 12 전에

line 10 동작을 수행하므로 전위 순회를 할 수 있다.

왼쪽, 오른쪽 자식으로 가기 전에 부모 노드가 자신의 일을 먼저 하는 것.

1 2 4 5 3 6 7

2. 중위 순회

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;    
 
void D(int x){
    if(x>7) return;
    else{
        D(x*2);
        printf("%d ", x);
        D(x*2+1);
    }
}    
 
int main(){
    D(1);
    return 0;
}

line 10 에서 왼쪽 자식 일이 다 끝나고 line 11 동작을 수행하므로

중위 순회를 할 수 있다.

왼쪽으로 쭉 내려간 후 왼쪽 자식 일이 다 끝나면 부모 노드 일을 한다.

4 2 5 1 6 3 7

3. 후위 순회

#include<stdio.h>
#include<vector>
#include<algorithm>
 
using namespace std;    
 
void D(int x){
    if(x>7) return;
    else{
        D(x*2);
        D(x*2+1);
        printf("%d ", x);
    }
}    
 
int main(){
    D(1);
    return 0;
}

line 10, 11 에서 왼쪽, 오른쪽 자식 일을 다 끝내고 line 12 동작을 수행하므로

후위 순회를 할 수 있다.

4 5 2 6 7 3 1    

--

순회로 재귀함수가 돌아가는 과정을 꼭 stack에 그려보면서 해보라고 하셨다.

기초가 튼튼해야 나중에 되돌아오는 일이 없을터이니

귀찮더라도 한번 해보자!

D(1) - line 10

--

D(2) - line 10

D(1) - line 10

--

D(4) - line 10

D(2) - line 10

D(1) - line 10

여기서 D(8) 과 D(9) 는 if(x>7) return 조건에 의해서 바로 함수가 종료된다.

그럼 D(4) 는 line 11 까지 돌았으므로 line 12 출력 동작을 수행한다.

4 를 출력하고 D(4) 는 stack 에서 제거된다.

D(2) - line 10

D(1) - line 10

--

D(2) - line 11

D(1) - line 10

--

D(5) - line 10

D(2) - line 11

D(1) - line 10

여기서 마찬가지로 D(10), D(11) 은 조건에 의해 바로 함수 종료

D(5) 는 5 출력 후 stack 에서 제거

D(1) - line 10

D(2) 도 line 11 까지 동작하였으니

2 출력 후 stack 에서 제거

D(1) - line 11

D(1) 은 다음 줄을 수행

D(3) - line 10

D(1) - line 11

--

D(6) - line 10

D(3) - line 10

D(1) - line 11

--

D(6) - line 10

D(3) - line 10

D(1) - line 11

D(12) 와 D(13) 은 조건에 의해 바로 함수 종료

D(6) 은 6을 출력하고 stack 에서 제거

D(3) - line 10

D(1) - line 11

--

D(3) - line 11

D(1) - line 11

D(3) 은 다음 line 동작

D(7) - line 10

D(3) - line 11

D(1) - line 11

D(14), D(15) 는 조건에 의해 바로 함수 종료

D(7) 은 7을 출력하고 stack 에서 제거

 

D(3) - line 11

D(1) - line 11

D(3) 도 line 11 까지 동작하였으므로 

3을 출력하고 stack 에서 제거

D(1) - line 11

D(1) 도 line 11 까지 동작하였으므로

1을 출력하고 stack 에서 제거

모든 함수가 동작하고 stack 이 비었으므로

main 함수로 돌아가게 된다.

이렇게 후위 순회의 과정을 stack 에 그려보았고

결과적으로 4 5 2 6 3 1 이 출력된다.