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

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

---

이진트리를 입력받고, 전위순회, 중위순회, 후위순회를 하면 된다.

트리에서의 순회는 재귀로 구현한다. 이때 전위, 중위, 후위에 따라 순회 순서가 달라지므로

이 부분만 약간 고려해서 재귀함수를 만들어주면 된다.

---

부분 코드 설명

int n;
vector<pair<int, int>> tree(26);

노드의 갯수를 n이라는 전역변수에 저장할것이다.

문제에서 주어지는것이 이진트리이기 때문에 pair형 벡터를 선언해

first로 왼쪽 자식, second로 오른쪽 자식을 저장한다.

 

void preorder(int depth) {
	printf("%c", depth + 'A');
	if (tree[depth].first != -1) {
		preorder(tree[depth].first);
	}
	if (tree[depth].second != -1) {
		preorder(tree[depth].second);
	}
}
void postorder(int depth) {
	if (tree[depth].first != -1) {
		postorder(tree[depth].first);
	}
	if (tree[depth].second != -1) {
		postorder(tree[depth].second);
	}
	printf("%c", depth + 'A');
}
void inorder(int depth) {

	if (tree[depth].first != -1) {
		inorder(tree[depth].first);
	}
	printf("%c", depth + 'A');
	if (tree[depth].second != -1) {
		inorder(tree[depth].second);
	}
}

전위, 중위, 후위 순회를 진행하는 코드이다. 셋 다 비슷한 구조를 가지고 있는데,

두개의 if문은 각각 왼쪽, 오른쪽 자식이 있다면 재귀호출을 통해 그 자식으로 내려가게 한다.

printf문의 위치가 절묘한데, 순회 순서에 따라 printf를 다른 위치에서 호출한다.

예를 들어 preorder(전위순회)의 경우에는 루트 - 왼쪽자식 - 오른쪽자식 순의 순회를 하기 때문에

어느 자식으로도 내려가기 전에 (=호출되자마자) 현재 노드를 출력한다.

 

char temp;
int index;
pair<char, char> buf;
cin >> temp;
cin >> buf.first >> buf.second;
index = temp - 'A';
if (buf.first == '.') {
    tree[index].first = -1;
}
else {
    tree[index].first = buf.first-'A';
}
if (buf.second == '.') {
    tree[index].second = -1;
}
else {
    tree[index].second = buf.second-'A';
}

부모-왼쪽자식-오른쪽자식의 순으로 "문자로" 입력되기 때문에

입력을 받은 뒤 A=0, B=1, ... 으로 저장해준다.

 

전체 코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n;
vector<pair<int, int>> tree(26);
void preorder(int depth) {
	printf("%c", depth + 'A');
	if (tree[depth].first != -1) {
		preorder(tree[depth].first);
	}
	if (tree[depth].second != -1) {
		preorder(tree[depth].second);
	}
}
void postorder(int depth) {
	if (tree[depth].first != -1) {
		postorder(tree[depth].first);
	}
	if (tree[depth].second != -1) {
		postorder(tree[depth].second);
	}
	printf("%c", depth + 'A');
}
void inorder(int depth) {

	if (tree[depth].first != -1) {
		inorder(tree[depth].first);
	}
	printf("%c", depth + 'A');
	if (tree[depth].second != -1) {
		inorder(tree[depth].second);
	}
}
int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		char temp;
		int index;
		pair<char, char> buf;
		cin >> temp;
		cin >> buf.first >> buf.second;
		index = temp - 'A';
		if (buf.first == '.') {
			tree[index].first = -1;
		}
		else {
			tree[index].first = buf.first-'A';
		}
		if (buf.second == '.') {
			tree[index].second = -1;
		}
		else {
			tree[index].second = buf.second-'A';
		}
	}
	preorder(0);
	printf("\n");
	inorder(0);
	printf("\n");
	postorder(0);
}

---