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

문제

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

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

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

입력

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

출력

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

---

아이디어

노드를 구조체로 선언하고, 이를 배열로 활용한다.
전위순회/중위순회/후위순회를 각각 재귀함수로 구현한다.

코드

#include <iostream>
using namespace std;

struct Node {
	char left;
	char right;
} node[26];
void preOrder(char alpha) {
	if (alpha == '.') {
		return;
	}
	char left = node[alpha - 'A'].left;
	char right = node[alpha - 'A'].right;

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

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

	postOrder(left);
	postOrder(right);
	cout << alpha;
}
int main() {
	int N;
	cin >> N;
	char nd, L, R;
	for (int i = 0; i < N; i++) {
		cin >> nd >> L >> R;
		node[nd - 'A'].left = L;
		node[nd - 'A'].right = R;
	}
	preOrder('A');
	cout << "\n";
	inOrder('A');
	cout << "\n";
	postOrder('A');
	cout << "\n";

	return 0;
}

시행착오

트리를 구현하는 방법을 몰라서 이 부분을 검색하느라 오래 걸렸다.
struct로 Node를 선언한 부분 끝자락에서 바로 초기화를 해주어도 되는지 몰라 고민했다.
검색 후 여러 코드를 살펴보고 다양한 방식으로 구현할 수 있음을 알았다.
이 코드를 참고하여 이해, 작성하였다.
입력이 제대로 이루어지지 않고 첫째줄을 입력했더니 'A'가 출력된 후 종료되어 이를 해결하기 위해 코드를 살펴보았는데, char형 변수를 int형 변수로 잘못 선언했기 때문임을 스스로 파악했다.