BOJ 1991 (트리 순회)

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

  

  
  예를 들어 위와 같은 이진 트리가 입력되면
  > 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
  > 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
  > 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)
  가 된다.
  
  
• 입력
  첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다.
  둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다.
  노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.
  
  
• 출력
  첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다.
  각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

#include<iostream>

using namespace std;
int N;
pair<char, char> node[26];
void fast_io() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
}

void input() {
	cin >> N;
	char parent, left_child, right_child;
	for (int i = 0; i < N; i++) {
		cin >> parent >> left_child >> right_child;
		node[parent - 'A'].first = left_child;
		node[parent - 'A'].second = right_child;
	}
}

void preorderTraversal(char current_node) {
	if (current_node != '.') {
		cout << current_node;
		preorderTraversal(node[current_node - 'A'].first);
		preorderTraversal(node[current_node - 'A'].second);
	}
}

void inorderTraversal(char current_node) {
	if (current_node != '.') {
		inorderTraversal(node[current_node - 'A'].first);
		cout << current_node;
		inorderTraversal(node[current_node - 'A'].second);
	}
}

void postorderTraversal(char current_node) {
	if (current_node != '.') {
		postorderTraversal(node[current_node - 'A'].first);
		postorderTraversal(node[current_node - 'A'].second);
		cout << current_node;
	}
}

int main() {
	fast_io();
	input();
	preorderTraversal('A');
	cout << '\n';
	inorderTraversal('A');
	cout << '\n';
	postorderTraversal('A');

	return 0;
}

   트리의 탐색 문제이다 알파벳 순서로 입력을 받기 때문에 index를 parent-'A'를 통해서 설정해주면 간단하게 해결할 수 있다.

각 탐색 방식에 따라 출력 및 재귀함수 호출 순서를 정해주었다.

전위 탐색(preorder) : 부모 -> 좌측 자식 -> 우측 자식

중위 탐색(inorder) : 좌측 자식 -> 부모 -> 우측 자식

후위 탐색(postorder) : 좌측 자식 -> 우측 자식 -> 부모

와 같은 순서로 호출해주면 된다.

시간 복잡도 : O(N)

숏코딩 -> 각 탐색 방법 별 함수를 따로 만들지 않는 코드

#include <bits/stdc++.h>
using namespace std;
map<char, pair<char, char> > a;
void t(char c, int i) {
  if (c == '.') return;
  if (i == 0) cout << c;
  t(a[c].first, i);
  if (i == 1) cout << c;
  t(a[c].second, i);
  if (i == 2) cout << c;
}
int main() {
  int n;
  cin >> n;
  char p;
  while (n--) cin >> p >> a[p].first >> a[p].second;
  for (int i = 0; i < 3; i++) {
    t('A', i);
    cout << "\n";
  }
}

i=0일때 전위 순회, 1일때 중위순회, 2일때 후위 순회를 적용한 것 같다
(if문에서 해당 숫자에 걸릴때만 문자 출력하고 왼쪽 자식, 오른쪽 자식 호출하는 부분은 조건문에 걸리지 않고 호출된다)