[백준] 트리 순회 1991번 C++ 풀이

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

1991번: 트리 순회

 

전체 코드

#include <iostream>
using namespace std;
pair<char, char> arr[26];
int N;
void preorder(char x)
{
	if (x!='.')
	{
		cout << x;
		preorder(arr[x-'A'].first);
		preorder(arr[x-'A'].second);
	}
}

void inorder(char x)
{
	if (x != '.')
	{
		inorder(arr[x - 'A'].first);
		cout << x;
		inorder(arr[x - 'A'].second);
	}
}
void postorder(char x)
{
	if (x != '.')
	{
		postorder(arr[x - 'A'].first);
		postorder(arr[x - 'A'].second);
		cout << x;
	}
}
int main(void)
{
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		char parent, left, right;
		cin >> parent >> left >> right;

		arr[(parent - 'A')].first = left;
		arr[(parent - 'A')].second=right;
	}
	preorder('A');
	cout << endl;
	inorder('A');
	cout << endl;
	postorder('A');
}

 

pair<char, char> arr[26];

pair로 만든 arr에

first는 left, second는 right를

arr[0]은 A를

arr[25]는 Z의 left, right를 담아줄 겁니다.

 

A를 0번
B를 1번

.... Z를 25번이라고 생각합시다.

	cin >> N;
	for (int i = 0; i < N; i++)
	{
		char parent, left, right;
		cin >> parent >> left >> right;

		arr[(parent - 'A')].first = left;
		arr[(parent - 'A')].second=right;
	}

parent-'A'를 해주면 A는 0으로 Z는 25로 만들 수 있습니다.

그것의 left와 right를 초기화시켜줍니다.

 

 

preorder('A');
cout << endl;
inorder('A');
cout << endl;
postorder('A');

모든 순회의 시작은 A부터 시작입니다.

N은 1 이상이라 무조건 A는 존재합니다.

 

전위 순회 preorder만 설명하자면

void preorder(char x)
{
	if (x!='.')
	{
		cout << x;
		preorder(arr[x-'A'].first);
		preorder(arr[x-'A'].second);
	}
}

현재 문자 x가 .이 아니라면

먼저 루트인 x를 출력해주고

left를 탐색합니다. ( 현재 x의 left(first)를 함수의 인자로 넘겨줍니다.)

right를 탐색합니다. ( 현재 x의 right(second)를 함수의 인자로 넘겨줍니다.)