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

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

1991번: 트리 순회

문제

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

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

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

가 된다.

입력

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

출력

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

---

재귀 문제이다. 각 노드별로 왼쪽, 오른쪽 노드를 기억한 다음 출력의 순서만 다르게 해주면 된다.

 

---

자료구조를 생각하고 재귀만 하면 된다는 생각에 바로 코드를 작성하였더니 입력이 제대로 안받아진 것 같다. char를 입력받기엔 cout이 적합하지 않았다. scanf를 활용했지만 다른 에러가 났다. 배열을 제대로 초기화 하지 않아서 그랬다. 배열을 초기화했지만 출력이 잘 되지 않았다. 입력을 first -> second 로 받아야 했는데 first->first로 두번 받아버렸다. 그래도 잘 나오지 않았다. + 'A'를 해주지 않아서 그랬다. 쉬운 문제인데 엄청나게 다양한 부분에서 틀렸다. 이런 시간을 줄여야 뒷문제에서 충분한 구상을 할 수 있을 것 같다.