[백준] C++ 1991번 트리 순회

문제

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

1991번: 트리 순회

 

접근 방법

트리를 순회하는 방법에 대한 문제이다.

먼저 트리를 구현하는 방법에는 여러 가지가 있는데 그중에서 map으로 트리를 구현하였다.

map의 key에 부모 노드를 저장하고, pair에는 각각 왼쪽 자식과 오른쪽 자식을 저장하였다.

순회는 재귀로 진행하여 자식 노드가 없을 때 종료되게 하였다.

 

코드

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

int n;
char leftChild, node, rightChild;
map<char, pair<char, char>> tree;

void preorder(char node) {
	cout << node;
	if (tree[node].first != '.') {
		preorder(tree[node].first);
	}
	if (tree[node].second != '.') {
		preorder(tree[node].second);
	}
}

void inorder(char node) {
	if (tree[node].first != '.') {
		inorder(tree[node].first);
	}
	cout << node;
	if (tree[node].second != '.') {
		inorder(tree[node].second);
	}
}

void postorder(char node) {
	if (tree[node].first != '.') {
		postorder(tree[node].first);
	}
	if (tree[node].second != '.') {
		postorder(tree[node].second);
	}
	cout << node;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> node >> leftChild >> rightChild;
		tree[node] = make_pair(leftChild, rightChild);
	}
	preorder('A');
	cout << '\n';
	inorder('A');
	cout << '\n';
	postorder('A');
}