백준 1991 - 트리 순회(C++)

문제 링크입니다. https://www.acmicpc.net/problem/1991

1991번: 트리 순회

트리의 순회 방식에 대해서 물어보는 문제입니다.

어떤 방식으로 트리를 순회하는지 이해한다면 풀 수 있는 문제입니다.

3가지 방법의 공통점은 항상 부모 노드인 'A'에서 시작한다는 것입니다.

'A' 노드에서 시작해서 어떤 방식으로 탐색하는지 한번 알아보겠습니다. 

 

1. 전위 순회

2. 중위 순회

3. 후위 순회

전위, 중위, 후위 순회가 어떤 방식으로 이뤄지는지 확인했습니다.

3가지 방식의 공통점은 모두 'A' 점에서 시작한다는 것입니다. 따라서 시작을 'A'에서 해주는 것이 중요합니다.

각 점은 자신이 부모일때 출력이 됩니다. 따라서 "부모 노드를 언제 출력하냐" 에 따라 출력 위치를 바꾸어주면 됩니다.

 

전위 순회를 통해 확인해보겠습니다.

void pre_order(char start){
	if(start == '.') return;
	cout << start;
	pre_order(node[start].first);
	pre_order(node[start].second);
}

전위 순회의 경우 부모 노드가 먼저 출력이 됩니다. 따라서 방문하자 마자 출력하는 것을 확인할 수 있습니다.

 

중위 순회를 확인해보겠습니다.

void In_order(char start){
	if(start == '.') return;
	In_order(node[start].first);
	cout << start;
	In_order(node[start].second);	
}

중위 순회의 경우 왼쪽 자식을 확인 후, 부모 노드가 출력됨을 확인할 수 있습니다. 따라서 왼쪽 자식을 확인 후, 자신을 출력해줍니다.

 

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#include <stack>

using namespace std;

int N;
typedef struct line{
	int first;
	int second;
}line;
vector<line> node(27);

void pre_order(char start){
	if(start == '.') return;
	cout << start;
	pre_order(node[start].first);
	pre_order(node[start].second);
}

void In_order(char start){
	if(start == '.') return;
	In_order(node[start].first);
	cout << start;
	In_order(node[start].second);	
}

void post_order(char start){
	if(start == '.') return;
	post_order(node[start].first);
	post_order(node[start].second);	
	cout << start;
}

int main() {
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++){
		char x, y, z;
		cin >> x >> y >> z;
		node[x].first = y;
		node[x].second = z;
	}
	pre_order('A');
	cout << "\n";
	In_order('A');
	cout << "\n";
	post_order('A');
	return 0;
}

 

 

 

자세한 것은 코드를 참고해주세요