[백준문제풀이] 1991 트리 순회

 

풀이일시 : 2020-12-27

 

 

문제 : 

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

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

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

가 된다.

 

 

입력 : 

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

 

 

출력 : 

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

 

 

풀이 : 

전위순회는 V / left / right

중위순회는 left / V / right

후위순회는 left / right / V

의 형태로 나타낼 수 있다.

 

입력시에 이진트리를 구성해주고 재귀를 통해 순회를 출력해준다.

 

//전위순회 중위순회 후위순회 구현

#include <iostream>
#include <vector>
using namespace std;

int N;
const int MAX = 26;
vector <pair<int,int>> v[MAX];

void preorder(int node) {
	cout << (char)(node + 'A');
	for (int i = 0; i < v[node].size(); i++) {
		preorder(v[node][i].first);
	}
}

void inorder(int node) {
	if (v[node].size() && v[node][0].second)
		inorder(v[node][0].first);
	cout << (char)(node + 'A');
	if (v[node].size() && !v[node][0].second)
		inorder(v[node][0].first);
	else if (v[node].size() == 2) {
		inorder(v[node][1].first);
	}
}

void postorder(int node)
{
	for (int i = 0; i < v[node].size(); i++)
		postorder(v[node][i].first);
	cout << (char)(node + 'A');
}

int main() {
	char a, b, c;
	cin >> N; //이진트리의 노드의 개수
	for (int i = 0; i < N; i++) {
		cin >> a >> b >> c;
		if (b != '.')
			v[a - 'A'].push_back({ b - 'A', 1 });
		if(c!='.')
			v[a - 'A'].push_back({ c - 'A', 0 });
	}
	preorder(0);
	cout << endl;
	inorder(0);
	cout << endl;
	postorder(0);
	cout << endl;
	return 0;
}