알고리즘 문제

[백준] 1991번 트리 순회

feelcoding 2020. 2. 12. 12:29
728x90

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

 

1991번: 트리 순회

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

www.acmicpc.net

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

map<char, pair<char, char>> m;

void preorder(char root) {
	cout << root;
	if (m[root].first != '.')
		preorder(m[root].first);
	if (m[root].second != '.')
		preorder(m[root].second);
}
void inorder(char root) {
	if (m[root].first != '.')
		inorder(m[root].first);
	cout << root;
	if (m[root].second != '.')
		inorder(m[root].second);
}
void postorder(char root) {
	if(m[root].first != '.')
		postorder(m[root].first);
	if(m[root].second != '.')
		postorder(m[root].second);
	cout << root;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char root, left, right;
		cin >> root >> left >> right;
		m[root] = make_pair(left, right);
	}
	preorder('A');
	cout << '\n';
	inorder('A');
	cout << '\n';
	postorder('A');
	return 0;
}

자료구조 시간에 배운 것과 이런 문제를 풀 때 사용하는 자료구조에는 조금 거리가 있는 것 같다.

트리 구조체나 클래스를 직접 만들지 않아도 이렇게 풀 수 있다.

https://breakcoding.tistory.com/205

 

[C++] 포인터 없이 map으로 이진트리 구현하기, 전위, 중위, 후위순회

C++로 트리 자료구조를 구현할 때에는 보통 왼쪽 자식을 가리키는 포인터, 오른쪽 자식을 가리키는 포인터, 내 데이터 이렇게 3가지 정보를 가지고 있는 Node라는 구조체를 만들어서 구현한다. 그런데 이 방법은..

breakcoding.tistory.com

처음에는 이진트리 클래스를 직접 만들었었는데 insert하는 과정에서 위상정렬을 해야 트리에 노드를 삽입할 수 있었다.

따라서 그냥 편리하게 map을 만들었다. 다른 사람들은 어떻게 트리를 구현했는지 찾아봐야겠다.

728x90