[백준] 1991 트리 순회 (C++)

백준 1991 트리 순회 문제
백준 1991 트리 순회 소스코드

📄 문제 설명

Problem

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

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

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

Input

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

Output

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

Example Input 1

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

Example Output 1

ABDCEFG
DBAECFG
DBEGFCA

📝 문제 해설

이 문제는 왼쪽 자식과 오른쪽 자식을 갖는 node라는 구조체를 만들어 해결하였다.
전위/중위/후위 순회는 재귀를 이용하며, 각 순회마다 출력과 재귀호출 순서를 조절하면 된다.

</> Source Code

#include <bits/stdc++.h>
#define MAX 26

using namespace std;

struct node{
	char left;
	char right;
};

vector<node> v(MAX);

void preOrder(char node){ // 전위 순회
	// root - left - right
	if(node == '.') return;
	
	printf("%c", node);
	preOrder(v[node].left);
	preOrder(v[node].right);
}

void inOrder(char node){ // 중위 순회
	// left - root - right
	if(node == '.') return;
	
	inOrder(v[node].left);
	printf("%c", node);
	inOrder(v[node].right);
}

void postOrder(char node){ // 후위 순회
	// left - right - root
	if(node == '.') return;
	
	postOrder(v[node].left);
	postOrder(v[node].right);
	printf("%c", node);
}

int main(){	
	int n;
	scanf("%d", &n);
	
	char rt, l, r;
	for(int i = 0; i < n; i++){
		cin >> rt >> l >> r;		
		v[rt].left = l;
		v[rt].right = r;
	}
	
	preOrder('A');
	printf("\n");
	
	inOrder('A');
	printf("\n");
	
	postOrder('A');
	
	return 0;
}