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

1991번 : 트리 순회

---

문제)

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

 

 

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

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

가 된다.

 

 

 

입력 :

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

 

 

 

출력 :

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

 

 

 

 

 

 

풀이)

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int n;
vector<int> lft (30, -1);
vector<int> rgt (30, -1);
 
// 전위 순회
void pre_order(int cur)
{
    if (cur == -1) return;
 
    cout << (char)(cur + 'A');
 
    pre_order(lft[cur]);
    pre_order(rgt[cur]);
}
 
// 중위 순회
void in_order(int cur)
{
    if (cur == -1) return;
 
    in_order(lft[cur]);
    cout << (char)(cur + 'A');
    in_order(rgt[cur]);
}
 
// 후위 순회
void post_order(int cur)
{
    if (cur == -1) return;
 
    post_order(lft[cur]);
    post_order(rgt[cur]);
    cout << (char)(cur + 'A');
}
 
int main() 
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
 
    cin >> n;
 
    char a, b, c;
    for (int i = 0; i < n; i++)
    {
 
        cin >> a >> b >> c;
        a -= 'A'; b -= 'A'; c -= 'A';
        
        if (b != '.' - 'A') lft[a] = b;
        if (c != '.' - 'A') rgt[a] = c;
    }
 
 
    pre_order(0);
    cout << "\n";
    in_order(0);
    cout << '\n';
    post_order(0);
 
    return 0;
}
 

---

출처 : https://www.acmicpc.net/problem/1991 

1991번: 트리 순회