백준 1991 트리 순회

www.acmicpc.net/problem/1991

1991번: 트리 순회

기초적인 트리 순회 문제.

처음에는 노드로 트리를 구현하여 순회시키려 했지만 생각보다 난이도가 있어서 배열로 구현했다.

이런 식으로 서브 노드가 더 이상 존재하지 않으면 '.'을 넣어 끝임을 표시한다.

	for (int i = 0; i < n; i++) {
		cin >> a >> b >> c;
		tree[a - 'A'][0] = b;
		tree[a - 'A'][1] = c;
	}

[0]은 왼쪽, [1]은 오른쪽으로 표현하여 각각의 아스키코드값으로 받아준다.

이렇게 하면 순회할 때

void preorder(char root) { //루트노드를 받아서
	if (root == '.') return;

	cout << root; //출력하고
	preorder(tree[root - 'A'][0]); //그 루트 노드의 왼쪽에 있는 서브노드를 재귀호출한다
	preorder(tree[root - 'A'][1]);
}

이런식으로 그 노드의 왼쪽, 오른쪽에 있는 노드를 재귀 호출해주면 된다.

 

#include <iostream>
using namespace std;

char tree[27][2];

void preorder(char root) {
	if (root == '.') return;

	cout << root;
	preorder(tree[root - 'A'][0]);
	preorder(tree[root - 'A'][1]);
}
void inorder(char root) {
	if (root == '.') return;

	inorder(tree[root - 'A'][0]);
	cout << root;
	inorder(tree[root - 'A'][1]);
}
void postorder(char root) {
	if (root == '.') return;

	postorder(tree[root - 'A'][0]);
	postorder(tree[root - 'A'][1]);
	cout << root;
}

int main() {
	int n;
	char a, b, c;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b >> c;
		tree[a - 'A'][0] = b;
		tree[a - 'A'][1] = c;
	}
	preorder('A');
	cout << endl;
	inorder('A');
	cout << endl;
	postorder('A');
	cout << endl;

	return 0;
}

 

잘 기억해둬야겠다.