C++ 백준 1991 트리 순회

백준 1991

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

1991번: 트리 순회

풀이 전 나의 생각

이진 트리를 입력 받아 전위 순회, 중위 순회, 후위 순회한 결과를 출력해야 한다.

 

조건

- N(1 ≤ N ≤ 26)

- 항상 A가 루트 노드가 된다.

 

과정

노드는 26개 만들 수 있기 때문에 노드의 값을 담을 배열은 데이터 타입 int, 크기를 27로 설정해준다.

 

A가 항상 루트 노드가 되기 때문에 전위, 중위, 후위 순회의 첫 시작은 무조건 A다.

 

이 문제를 풀기 위해선 전위 순회, 중위 순회, 후위 순회에 대한 사전 지식이 필요하다.

 

<사전 지식>

https://tjdgh7419.tistory.com/187

[오늘의 지식] 트리의 순회

 

 

1. 노드의 주어진 정보를 저장한다.

for (int i = 0; i < N; i++)
	{
		char p, l, r;
		cin >> p >> l >> r;

		if(l != '.') lc[p - 'A' + 1] = l - 'A' + 1;
		if(r != '.') rc[p - 'A' + 1] = r - 'A' + 1;
	}

문자 그대로의 값을 받아서 저장해도 되지만 아무래도 숫자로 바꿔서 진행하는 것이 더욱 편하기 때문에

문자를 char에서 int로 바꿔준다.

 

2. 순서에 맞게 전위, 중위, 후위 순회를 진행한다.

void preorder(int cur)
{
	char node = (char)(cur + 'A' - 1);

	cout << node;
	if(lc[cur] != 0) preorder(lc[cur]);
	if (rc[cur] != 0) preorder(rc[cur]);
}

void inorder(int cur)
{
	char node = (char)(cur + 'A' - 1);

	if (lc[cur] != 0) inorder(lc[cur]);
	cout << node;
	if (rc[cur] != 0) inorder(rc[cur]);
}

void postorder(int cur)
{
	char node = (char)(cur + 'A' - 1);

	if (lc[cur] != 0) postorder(lc[cur]);
	if (rc[cur] != 0) postorder(rc[cur]);
	cout << node;
}

문자를 출력해주기 위해 현재 메서드에서 받은 값을 char로 되돌려준다.

다음으로 각 순회에 맞는 순서에 따라 재귀함수를 실행시켜주면 알맞은 순서로

현재 탐색하고 있는 노드의 값이 출력된다.

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

int lc[27];
int rc[27];

void preorder(int cur)
{
	char node = (char)(cur + 'A' - 1);

	cout << node;
	if(lc[cur] != 0) preorder(lc[cur]);
	if (rc[cur] != 0) preorder(rc[cur]);
}

void inorder(int cur)
{
	char node = (char)(cur + 'A' - 1);

	if (lc[cur] != 0) inorder(lc[cur]);
	cout << node;
	if (rc[cur] != 0) inorder(rc[cur]);
}

void postorder(int cur)
{
	char node = (char)(cur + 'A' - 1);

	if (lc[cur] != 0) postorder(lc[cur]);
	if (rc[cur] != 0) postorder(rc[cur]);
	cout << node;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		char p, l, r;
		cin >> p >> l >> r;

		if(l != '.') lc[p - 'A' + 1] = l - 'A' + 1;
		if(r != '.') rc[p - 'A' + 1] = r - 'A' + 1;
	}

	preorder(1); cout << '\n';
	inorder(1); cout << '\n';
	postorder(1); cout << '\n';
}