[BOJ 백준] 트리 순회(1991) C++

 

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

1991번: 트리 순회

 

문제 설명 : 

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

예를 들어 위와 같은 이진 트리가 입력되면,

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

가 된다.

 

입력 : 

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파벳 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현한다.

출력 : 

첫째 줄에 전위 순회, 둘째 줄에 중위 순회, 셋째 줄에 후위 순회한 결과를 출력한다. 각 줄에 N개의 알파벳을 공백 없이 출력하면 된다.

 

예제 입력 : 

7
A B C
B D .
C E F
E . .
F . G
D . .
G . .

예제 출력 : 

ABDCEFG
DBAECFG
DBEGFCA

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 트리순회 1991 C++
#if 1
#pragma warning(disable:4996)
#include <cstdio>
#include <vector>

#define MAX (26)

using namespace std;

typedef struct st{
	char left;
	char right;
}node;

node tree[MAX];

int N;

void input();
void preOrder(char nodeId);
void centerOrder(char nodeId);
void postOrder(char nodeId);


int main() {
	// 1. 입력받음
	//freopen("input.txt", "r", stdin);
	input();
	

	preOrder('A');
	printf("\n");

	centerOrder('A');
	printf("\n");

	postOrder('A');

	return 0;
}

void input() {
	scanf("%d", &N);

	char root, left, right;
	for (int i = 0; i < N; i++) {
		scanf(" %c %c %c", &root, &left, &right);
		tree[root - 'A'].left = left;
		tree[root - 'A'].right = right;
	}
}


// 전위 순회
void preOrder(char nodeId) { 
	// root - left - right
	if (nodeId == '.') return;

	printf("%c", nodeId);
	preOrder(tree[nodeId-'A'].left);
	preOrder(tree[nodeId-'A'].right);
}

// 중위 순회
void centerOrder(char nodeId) {
	// left - root - right
	if (nodeId == '.') return;

	centerOrder(tree[nodeId-'A'].left);
	printf("%c", nodeId);
	centerOrder(tree[nodeId - 'A'].right);
}

// 후위 순회
void postOrder(char nodeId) {
	// left - right - root
	if (nodeId == '.') return;

	postOrder(tree[nodeId - 'A'].left);
	postOrder(tree[nodeId - 'A'].right);
	printf("%c", nodeId);
}

#endif