[C++] 백준 1991 : 트리 순회

 

 

 

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

 

 

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

 

 

입력

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

 

 

출력

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

 

---

 

 

문제 해결

이 문제는 입력의 갯수가 최대 26개 뿐이므로 각 노드와 그의 왼쪽, 오른쪽 자식을 입력 받을 때마다 탐색하면서 해당 노드와 자식 노드를 연결시켜 실제 트리 구조로 만들어서 풀 수 있지만 범용적이지 않다.

​

만일 입력의 갯수가 1000, 10000처럼 커진다면 부모와 자식 노드를 연결짓기 위해 매번 탐색하는 위 방법은 매우 비효율적이기 때문이다.

​

그래서 왼쪽 자식과 오른쪽 자식의 정보를 담고있는 노드를 배열로 선언해서 현재 노드가 영어 대문자이면 순회를 하는 재귀함수로 구현하였다.

 

 

 

코드

#include <iostream>
using namespace std;

int n, root = 'A';
char p, c1, c2;

struct Node {
    char left, right;
};

Node ary[26];

void pre(char current) {
    if (current >= 'A' && current <= 'Z') {
        cout << current;
        pre(ary[current - root].left);
        pre(ary[current - root].right);
    }
}

void in(char current) {
    if (current >= 'A' && current <= 'Z') {
        in(ary[current - root].left);
        cout << current;
        in(ary[current - root].right);
    }
}

void post(char current) {
    if (current >= 'A' && current <= 'Z') {
        post(ary[current - root].left);
        post(ary[current - root].right);
        cout << current;
    }
}

int main() {
    cin >> n;

    while (n--) {
        cin >> p >> c1 >> c2;

        ary[p - root].left = c1;
        ary[p - root].right = c2;
    }

    pre(root);  cout << endl;
    in(root);   cout << endl;
    post(root);
}