[백준] 1991 트리 순회

[문제]

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

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

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

[입력]

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

[출력]

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

[예제 입력]

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

[예제 출력]

ABDCEFG
DBAECFG
DBEGFCA

Tree Traversal

1. 전위순회 : VLR
2. 중위순회 : LVR
3. 후위순회 : LRV

CONCEPT

배열로 트리를 구현한다. root는 알파벳 전체가 될 수 있으므로, 크기를 대문자 개수인 26으로 설정한다. Tree[0][0]은 'A'노드의 왼쪽 자식을 의미하고, Tree[0][1]은 'A' 노드의 오른쪽 자식을 의미한다. '.'이 입력된 경우 -1을 저장한다.
순회 함수는 재귀를 이용하여 구현하였다.

#include <stdio.h>
#include <iostream>
using namespace std;

void inorder(int tree[][2], int root) {
	if (root == -1) return;
	inorder(tree, tree[root-'A'][0]);
	printf("%c", root);
	inorder(tree, tree[root - 'A'][1]);
}
void preorder(int tree[][2], int root) {
	if (root == -1) return;
	printf("%c", root);
	preorder(tree, tree[root - 'A'][0]);
	preorder(tree, tree[root - 'A'][1]);
}
void postorder(int tree[][2], int root) {
	if (root == -1) return;
	postorder(tree, tree[root - 'A'][0]);
	postorder(tree, tree[root - 'A'][1]);
	printf("%c", root);
}

int main() {
	int node_num;
	int Tree[26][2]; 
	char root, right, left;
	cin >> node_num;

	while (node_num--) {
		cin >> root >> left >> right;
		if (left == '.' && right == '.') {
			Tree[root - 'A'][0] = -1;
			Tree[root - 'A'][1] = -1;
		}
		else if (left == '.' && right != '.') {
			Tree[root - 'A'][1] = right;
			Tree[root - 'A'][0] = -1;
		}
		else if (left != '.' && right == '.') {
			Tree[root - 'A'][0] = left;
			Tree[root - 'A'][1] = -1;
		}
		else {
			Tree[root - 'A'][0] = left;
			Tree[root - 'A'][1] = right;
		}
	}

	preorder(Tree, 'A');
	printf("\n");
	inorder(Tree, 'A');
	printf("\n");
	postorder(Tree, 'A');

	return 0;
}