이진트리의 깊이우선탐색(DFS) (+전위순회, +중위순회, +후위순회)

문제인식)

다음과 같은 이진트리가 있다.

위 트리를 전위순회, 중위순회, 후위순회하려면 어떻게 해야할까?

 

참고로 전위순회, 중위순회, 후위순회에 대한 이름이 붙은 기준은

루트노드에 대한 작업순서를 기준으로 이름이 붙었다고 생각하면 쉬울 것이다.

 

즉,

루트노드를 먼저 작업한다면 전위순회 (루트노드 → 왼쪽서브트리 → 오른쪽서브트리),

루트노드를 중간에 작업한다면 중위순회 (왼쪽서브트리 → 루트노드 → 오른쪽서브트리),

루트노드를 마지막에 작업한다면 후위순회 (왼쪽서브트리 → 오른쪽서브트리 → 루트노드)

가 되는 것이다.

 

이렇게 각 순회에 따른 출력 결과는 다음과 같아야 할 것이다.

전위순회	1 2 4 5 3 6 7
중위순회	4 2 5 1 6 3 7
후위순회	4 5 2 6 7 3 1

 

왜 이렇게 나오는지 전위순회를 기준으로 설명을 하자면

전위순회

 

루트노드 "1"에 대한 작업(출력)을 하고,

1 //현재까지의 출력

"1"의 왼쪽서브트리에 접근한다. ("1"의 오른쪽서브트리는 왼쪽서브트리의 작업이 끝난 후 진행)

 

접근한 왼쪽서브트리의 루트노드 "2"에 대한 작업(출력)을 하고,

1 2 //현재까지의 출력

"2"의 왼쪽서브트리에 접근한다. ("2"의 오른쪽서브트리는 왼쪽서브트리의 작업이 끝난 후 진행)

 

접근한 왼쪽서브트리의 루트노드 "4"에 대한 작업(출력)을 하고,

1 2 4 //현재까지의 출력

"4"의 왼쪽서브트리는 없으므로 "4"의 루트노드인 "2"로 회귀

 

"2"의 왼쪽서브트리에 대한 작업이 끝났으므로 "2"의 오른쪽서브트리에 접근한다.

 

접근한 왼쪽서브트리의 루트노드 "5"에 대한 작업(출력)을 하고,

1 2 4 5 //현재까지의 출력

.

.

.

이후 이런식으로 반복이 되는 것이다. (재귀가 생각나지 않은가?)

 

마찬가지로 중위순회, 후위순회에 따른 접근순서를 gif로 묘사하자면 다음과 같다.

중위순회

 

후위순회

 

이를 이제 재귀로 풀어볼 것이다.

 

해결과정)

사실 문제인식만 잘하여도 절반을 푼 것이나 마찬가지이다.

이제 나머지 절반을 완성시켜보자.

 

전위순회를 의사코드로 풀어보자면

void 함수(현재노드) {
    기저조건을 설정한다.

    현재노드에 대한 작업을 한다.  //전위, preorder
    함수(왼쪽 서브트리의 루트노드);
    함수(오른쪽 서브트리의 루트노드);
}

가 된다. (마찬가지로 중위순회, 후위순회에 대한 의사코드도 쉽게 작성할 수 있을 것이다.)

 

이제 실제로 작동하는 코드(여기서는 C++)로 옮기기 위해 몇가지 설정을 하자면...

 

1) 트리의 루트노드이자 시작점은 "1"로 설정한다.

2) 기저조건은 7을 넘어가면 종료하도록 설정한다.

3) 작업은 단순히 현재노드의 번호를 출력하는 것으로 설정한다.

4) 왼쪽(루트)노드는 본 노드의 번호 × 2로 접근한다.

5) 오른쪽(루트)노드는 본 노드의 번호 × 2 + 1로 접근한다.

 

이제 전위 순회를 실제 코드로 작성해보자.

#include<cstdio>

void preOrder(int n) {
    if(n>7) return; //기저조건

    printf("%d ", n); //전위
    preOrder(n*2);    //왼쪽 서브트리의 루트노드
    preOrder(n*2+1);  //오른쪽 서브트리의 루트노드
}

int main() {

    preOrder(1); // 1에서부터 트리탐색 시작

    return 0;
}

 

나머지 중위순회, 후위순회도

작업(출력)과 접근의 순서만 바꾸면

완성이다. (여기서는 함수만 작성, 메인함수에서는 똑같이 1부터 시작하도록 하면 된다.)

 

void inOrder(int n) {
    if(n>7) return; //기저조건 

    inOrder(n*2);    //왼쪽 서브트리의 루트노드
    printf("%d ", n);//중위
    inOrder(n*2+1);  //오른쪽 서브트리의 루트노드
}

 

void postOrder(int n) {
    if(n>7) return; //기저조건 

    postOrder(n*2);    //왼쪽 서브트리의 루트노드
    postOrder(n*2+1);  //오른쪽 서브트리의 루트노드
    printf("%d ", n);  //후위
}

 

예시는 단순하게 했지만,

작업할 노드의 번호를 객체의 속성으로 대신하거나,

작업을 단순히 출력만 하는 것이 아닌, 여러 작업으로 대신한다면

수많고 놀라우리만큼 확장성있는 프로그래밍을 할 수 있을 것이다.