뚝딱뚝딱

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

💡 트리 순회

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

예를 들어 위와 같은 이진 트리가 입력되면,
전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)가 된다.

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

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

✅ 문제 풀이

• 트리를 전위, 중위, 후위 순회하는 방법은 각각의 함수를 재귀호출하는 방법이다.
• 트리를 int타입의 2차원 배열에 넣을건데, 각 노드는 입력으로 받는 노드 즉 알파벳에서 'A'를 뺀 값을 인덱스로 받을 것이다. 따라서 A부터이므로, 0~25까지 인덱스를 사용하게 될 것이다. 그 인덱스의 첫번째 요소에는 left자식이, 두번째 요소에는 right자식이 들어가는 것이다.
• 따라서 left에는 두번째로 입력받은 문자가 .이 아닐 경우 문자-'A' 한 값을 넣어주고, right도 세번째로 입력받은 문자에 대해 동일하게 처리한다.
• 만약 문자가 .이라면 -1을 넣도록 한다.
• preorder(n)함수를 선언한다. 이 함수는 노드 n부터 탐색할 것인데, 만약 n이 -1이라면 없는 노드인 것이므로 return하도록 하고, 그렇지 않다면 node n을 알파벳으로 출력하기 위해 n+'A'를 하여 알파벳으로 출력한다. 그런후 preorder(arr[n][0])와 preorder(arr[n][1])을 차례로 호출하여 재귀 호출되도록 한다.
• inorder(n)함수를 선언한다. 이 함수는 노드 n부터 탐색할 것인데, 만약 n이 -1이라면 없는 노드인 것이므로 return하도록 하고, 그렇지 않다면 inorder(arr[n][0])를 호출한 후, n을 알파벳으로 출력하고, inorder(arr[n][1])을 호출한다.
• postorder(n)함수를 선언한다. 이 함수는 노드 n부터 탐색할 것인데, 만약 n이 -1이라면 없는 노드인 것이므로 return하도록 하고, 그렇지 않다면 postorder(arr[n][0])와 postorder(arr[n][1])을 호출한 후, n을 알파벳으로 출력한다.
• 각각의 함수들을 main함수에서 n=0으로 시작해 호출하고 결과를 확인한다.

✏ 코드 전문

#include<iostream>
#include<vector>
#include<string>
#include<math.h>

using namespace std;


void preorder(int n, vector<vector<int>> &arr) {
	if (n == -1) return;
	cout << (char)(n + 'A');
	preorder(arr[n][0], arr);
	preorder(arr[n][1], arr);
}
void inorder(int n, vector<vector<int>> &arr) {
	if (n == -1) return;
	inorder(arr[n][0], arr);
	cout << (char)(n + 'A');
	inorder(arr[n][1], arr);
}
void postorder(int n, vector<vector<int>> &arr) {
	if (n == -1) return;
	postorder(arr[n][0], arr);
	postorder(arr[n][1], arr);
	cout << (char)(n + 'A');
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n;
	cin >> n;

	vector<vector<int>> arr(n);

	for (int i = 0; i < n; i++) {
		char node, l, r;
		cin >> node >> l >> r;
		int x = node - 'A';
		if (l == '.') {
			arr[x].push_back(-1);
		}
		else arr[x].push_back(l-'A');
		if (r == '.') {
			arr[x].push_back(-1);
		}
		else arr[x].push_back(r - 'A');
	}

	preorder(0, arr);
	cout << "\n";
	inorder(0, arr);
	cout << "\n";
	postorder(0, arr);
	cout << "\n";

	return 0;
}