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

 

1) 문제설명

백준 Online Judge 1991번 트리 순회

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

1991번: 트리 순회

 

2) 아이디어

트리를 구조체가 아닌 2차 배열로 구현하였다.

nodes [][0] : 왼쪽 자식, nodes [][1] : 오른쪽 자식으로 설정한다.

왼쪽 입력이. 일 경우 -1을 할당, 마찬가지로 오른쪽 입력이. 일 경우 -1을 할당하고 나머지를 자식들로 할당한다.

이후 순서대로 전위, 중위, 후위 순회 순으로 출력한다.

 

3) 코드

#include<iostream>
#include<queue>
#include<deque>
#include<string.h>
#include<math.h>
#include<cmath>
#include<stack>
#include<algorithm>

using namespace std;
int n;
char nodes[27][2]; // nodes[][0] : 왼쪽자식 nodes[][1] : 오른쪽자식

void preorder(int a) {
	if (a == -1) {
		return;
	}
	printf("%c", a + 'A');
	preorder(nodes[a][0]);
	preorder(nodes[a][1]);
}


void inorder(int a) {
	if (a == -1) {
		return;
	}
	inorder(nodes[a][0]);
	printf("%c", a + 'A');
	inorder(nodes[a][1]);
}

void postorder(int a) {
	if (a == -1) {
		return;
	}
	postorder(nodes[a][0]);
	postorder(nodes[a][1]);
	printf("%c", a + 'A');
}


int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		char C, L, R;
		cin >> C >> L >> R;
		if (L == '.') { // 왼쪽자식이 .일 경우 왼쪽자식에게 -1 할당
			nodes[C - 'A'][0] = -1;
		}
		else { // 왼쪽자식이 .이 아닐 경우
			nodes[C - 'A'][0] = L - 'A';
		}

		if (R == '.') {
			nodes[C - 'A'][1] = -1;
		}
		else {
			nodes[C - 'A'][1] = R - 'A';
		}
	}
	preorder(0);
	cout << endl;
	inorder(0);
	cout << endl;
	postorder(0);

}