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

1991번: 트리 순회 문제 바로가기

문제 분석

노드 개수와 각 노드와 왼쪽 자식 노드, 오른쪽 자식 노드가 입력으로 주어진다.

노드의 이름은 A부터 차례대로 알파벳 대문자로 주어지고, 항상 A가 루트노드이며 자식노드 없는 경우 .으로 표현된다.

이 때, 이 트리를 전위 순회, 중위 순회, 후위 순회한 결과를 순서대로 출력하면 되는 문제이다.

---

문제 풀이 과정

1. 트리의 왼쪽과 오른쪽 자식을 저장할 수 있는 구조 만들자.

   struct Node {
       char left;
       char right;
   };
   
   Node tree[MAX];

2. 각 노드와 왼쪽 노드, 오른쪽 노드를 입력 받아 트리 구조 만들자.

   for (int i = 0; i < N; i++) {
           cin >> node >> left >> right;
           tree[node - 'A'].left = left;
           tree[node - 'A'].right = right;
   }

3. 전위 순회(루트)(왼쪽 자식)(오른쪽 자식) 구현하자.

   void preorder(char node) {
       if (node == '.')
           return;
       cout << node; // 루트
       preorder(tree[node - 'A'].left); // 왼쪽 자식
       preorder(tree[node - 'A'].right); // 오른쪽 자식
   }

4. 중위 순회(왼쪽 자식)(루트)(오른쪽 자식)와 후위 순회(왼쪽 자식)(오른쪽 자식)(루트) 구현하자.

   // 중위 순회
   void inorder(char node) {
       if (node == '.')
           return;
       inorder(tree[node - 'A'].left);
       cout << node;
       inorder(tree[node - 'A'].right);
   }
   
   // 후위 순회
   void postorder(char node) {
       if (node == '.')
           return;
       postorder(tree[node - 'A'].left);
       postorder(tree[node - 'A'].right);
       cout << node;
   }

5. 전위 순회, 중위 순회, 후위 순회 순서대로 출력하자.

   preorder('A');
   cout << "\n";
   inorder('A');
   cout << "\n";
   postorder('A');
   cout << "\n";

---

코드

#include<iostream>
#define MAX 27
using namespace std;

struct Node {
    char left;
    char right;
};

Node tree[MAX];
int N;

void preorder(char node) {
    if (node == '.')
        return;
    cout << node;
    preorder(tree[node - 'A'].left);
    preorder(tree[node - 'A'].right);
}

void inorder(char node) {
    if (node == '.')
        return;
    inorder(tree[node - 'A'].left);
    cout << node;
    inorder(tree[node - 'A'].right);
}

void postorder(char node) {
    if (node == '.')
        return;
    postorder(tree[node - 'A'].left);
    postorder(tree[node - 'A'].right);
    cout << node;
}

int main() {
    cin >> N;
    char node, left, right;
    for (int i = 0; i < N; i++) {
        cin >> node >> left >> right;
        tree[node - 'A'].left = left;
        tree[node - 'A'].right = right;
    }

    preorder('A');
    cout << "\n";
    inorder('A');
    cout << "\n";
    postorder('A');
    cout << "\n";
}