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

1991번: 트리 순회 (acmicpc.net)

1991번: 트리 순회

---

이해하기 

트리 순회 3가지

전위 순회 (preorder) : 현재 노드 - 왼쪽 노드 - 오른쪽 노드
중위 순회 (inorder) : 왼쪽 노드 - 현재 노드 - 오른쪽 노드
후위 순회 (postorder) : 왼쪽 노드 - 오른쪽 노드 - 현재 노드

위 3가지 트리 순회는 해당하는 순서대로 함수로 재귀적으로 호출해 구현할 수 있다.
 
[백준] 1991번 : 트리 순회 [C/C++] — 백준 하루 한 문제 (tistory.com)

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

[백준/C++]#1991 - 트리 순회 (tistory.com)

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

 

---

최종코드

#include <iostream>
using namespace std;

int a[50][2];

//전위 순회 
void preorder (int n) {
	if (n == -1) return;
	cout << (char)(n+'A');
	preorder(a[n][0]);
	preorder(a[n][1]);
}

//중위 순회
void inorder (int n) {
	if (n == -1) return;
	inorder(a[n][0]);
	cout << (char)(n+'A');
	inorder(a[n][1]);
}

//후위 순회
void postorder (int n) {
	if (n == -1) return;
	postorder(a[n][0]);
	postorder(a[n][1]);
	cout << (char)(n+'A');
}

int main() {
	int n;
	cin >> n;
	for (int i=0; i<n; i++) {
		char x, y, z;
		cin >> x >> y >> z;	
		x = x-'A';		// char to int 

      //주어진 트리를 저장
      
      //왼쪽 노드가 없는 경우
		if (y == '.') {	
			a[x][0] = -1;
		}
		else {
			a[x][0] = y-'A';
		}
      //왼쪽 노드가 없는 경우
		if(z == '.') {
			a[x][1] = -1;
		}
		else {
			a[x][1] = z-'A';
		}
	}
	preorder(0); cout << '\n';
	inorder(0); cout << '\n';
	postorder(0);

	return 0;
}