1991번 트리순회

백준 온라인 저지 1991번 트리순회

---

문제 출처 : https://www.acmicpc.net/problem/1991

풀이 과정

해당 문제는 각각의 노드가 왼쪽과 오른쪽의 자식 노드를 가질 수 있는 구조인 이진 트리입니다. 따라서 구조체를 사용하여 노드를 만들었고, 여러개의 노드를 사용하므로 구조체 배열을 선언했습니다.

입력을 정수가아닌 문자로 받기 때문에 이를 구조체 배열의 인덱스와 매칭시키기 위해서는 정수로의 변환이 필요하기 때문에 아스키코드를 연산하여 배열에 저장할 수 있도록 했습니다.

순회는 일반적으로 사용하는 재귀함수를 사용하여 구현했습니다. 루트가 탐색되는 순서에 따라 전위 순회, 중위 순회, 후위 순회로 나뉘어집니다. 

<전위 순회>

루트 -> 왼쪽 -> 오른쪽

<중위 순회>

왼쪽 -> 루트 -> 오른쪽

<후위 순회>

왼쪽 -> 오른쪽 -> 루트

소스 코드

#include <iostream>

using namespace std;

struct Node {
	char left;
	char right;
};

Node node[26];

void pre_order(char alpha) {
	if(alpha =='.') return;
	char left = node[alpha-'A'].left;
	char right = node[alpha-'A'].right;
	
	cout << alpha;
	pre_order(left);
	pre_order(right);
}

void in_order(char alpha){
	if(alpha =='.') return;

	char left = node[alpha-'A'].left;
	char right = node[alpha-'A'].right;
	
	in_order(left);
	cout << alpha;
	in_order(right);
	
}

void post_order(char alpha){
	if(alpha =='.') return;

	char left = node[alpha-'A'].left;
	char right = node[alpha-'A'].right;
	
	post_order(left);
	post_order(right);
	cout << alpha;
	
}

int main() {
	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;
	for(int i=0;i<n;i++) {
		char a,b,c;
		cin >> a >> b >> c;
		node[a-'A'].left = b;
		node[a-'A'].right = c;
	}
		
	pre_order('A');
	cout << '\n';
	
	in_order('A');
	cout << '\n';
	
	post_order('A');
	cout << '\n';	
}