[자료구조] 백준 1991번: 트리 순회 (C++)

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

1991번: 트리 순회

트리 순회에는 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)를 제외하고도 여러 가지 순회 방법이 있다.

이번 문제에서는 3가지 순회만 다룬다.

• 전위 순회(preorder traversal): [루트] [왼쪽 서브 트리] [오른쪽 서브 트리]
• 중위 순회(inorder traversal): [왼쪽 서브 트리] [루트] [오른쪽 서브트리]
• 후위 순회(postorder traversal): [왼쪽 서브트리] [오른쪽 서브트리] [루트]

서브 트리로 간다고 한 이유는 노드라고 표현하기에는 이해하기 쉽지 않기 때문에 서브 트리라는 표현을 썼다.

중위 순회를 예로 들어보면

('어디부터 처음 순회가 된다.'라는 표현이 껄끄러워 '도달한다'는 표현을 사용했다.)

A(루트 노드)부터 시작했을 때, 왼쪽에 서브 트리가 존재하므로 B로간다. B에도 왼쪽 서브트리 D가 존재하므로

1. 맨 처음에는 D에 도달한다.

2. 그다음 D의 parent노드인 B에 도달한다.

3. B의 오른쪽 서브 트리는 없으므로 A에 도달한다.

4. 왼쪽 서브 트리와 루트의 순회가 끝났다.

5. 오른쪽 서브 트리로 가서 C부터 시작해서 또 왼쪽 서브 트리부터 순회를 시작한다.

결과: DBAECFG

---

코드로는 어떻게 구현을 하는가?

'.'가 없다는 뜻이므로 '.'일 때는 종료를 시키고, 리커시브를 이용하여 구현할 수 있다.

단, 각 순회마다 언제 출력을 하는지가 중요하다.

리커시브는 함수조차 트리의 관점에서 생각하면 더 쉽게 접근할 수 있다.

다음에 업 솔빙 해보면 좋을 문제 같다.

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

int n;
char tree[26][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() {
	cin >> n;
	char parent, left, right;
	for (int i = 0; i < n; i++) {
		cin >> parent >> left >> right;
		tree[parent - 'A'][0] = left;
		tree[parent - 'A'][1] = right;
	}

	preorder('A');
	cout << '\n';

	inorder('A');
	cout << '\n';

	postorder('A');
	cout << '\n';

	return 0;
}