백준, boj) 1991. 트리순회 ( C / C++)

1. 문제 링크

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

1991번: 트리 순회

 

2. 문제 개요

전위, 중위, 후위 순회한 결과를 출력하자.

 

 

3. 문제 힌트

 재귀 함수로 구현해야 한다.

전, 중, 후위는 값을 출력하는 시간이다.

 

4. 문제풀이

재귀 함수에 익숙하지 않은 분들이 책에서만 본 내용을 구현하기엔 쉽지 않을 것이다.

 

전위 순회를 예로 들면

방문하자마자 출력하고,  왼쪽 자식이 존재하면 왼쪽자식을 방문한다.

위의 절차를 반복하고 왼쪽자식이 없다면 이제 오른쪽 자식을 방문한다.

오른쪽 자식을 방문했을 때도 마찬가지이다. 출력 -> 왼쪽 자식 확인 -> 오른쪽 자식 확인

이런 순서이다.

 

중위 순회는 왼쪽 자식 확인 -> 출력 -> 오른쪽 자식 확인

후위 순회는 왼쪽자식확인 -> 오른쪽 자식 확인 -> 출력

과 같은 방식이다.

 

재귀 함수에 익숙하지 않으신 분이 코드를 보면 잘 이해가 안 될 수도 있지만, 한번 확인하고 이 문제를 통해 익히도록 합시다.

 

 

5. 코드

#include <iostream>
using namespace std;

struct node {
	int left, right;
}NODE[26];

void preorder(int cur)
{
	cout << (char)(cur + 'A');
	if (NODE[cur].left != -1)
		preorder(NODE[cur].left);
	if (NODE[cur].right != -1)
		preorder(NODE[cur].right);
	return;
}
void inorder(int cur)
{
	if (NODE[cur].left != -1)
		inorder(NODE[cur].left);
	cout << (char)(cur + 'A');
	if (NODE[cur].right != -1)
		inorder(NODE[cur].right);
	return;
}
void postorder(int cur)
{
	if (NODE[cur].left != -1)
		postorder(NODE[cur].left);
	if (NODE[cur].right != -1)
		postorder(NODE[cur].right);
	cout << (char)(cur + 'A');
	return;
}
int main()
{
	int n;
	cin >> n;

	for (int i = 0; i < 26; ++i)
		NODE[i].left = NODE[i].right = -1;
	
	for (int i = 0; i < n; ++i)	{
		char p, l, r;
		cin >> p >> l >> r;
		if (l != '.')
			NODE[p - 'A'].left = l - 'A';
		if (r != '.')
			NODE[p - 'A'].right = r - 'A';
	}
	preorder(0);
	cout << '\n';
	inorder(0);
	cout << '\n';
	postorder(0);

	return 0;
}

6. 결과 사진

지적, 댓글 언제나 환영입니다~