백준 1991번 C++

백준 1991번 트리 순회
https://www.acmicpc.net/problem/1991

1991번: 트리 순회

정답 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdio>
#define ull long long int
using namespace std;
struct Node
{
	int ID;
	Node* Left;
	Node* Right;
};
Node* arr[30];
void preorder(Node *n)
{
	cout << char(n->ID + 'A');
	if (n->Left != nullptr)
		preorder(n->Left);
	if (n->Right != nullptr)
		preorder(n->Right);
	return;
}
void inorder(Node* n)
{
	if (n->Left != nullptr)
		inorder(n->Left);
	cout << char(n->ID + 'A');
	if (n->Right != nullptr)
		inorder(n->Right);
	return;
}
void postorder(Node* n)
{
	if (n->Left != nullptr)
		postorder(n->Left);
	if (n->Right != nullptr)
		postorder(n->Right);
	cout << char(n->ID + 'A');
	return;
}
int main(void)
{
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		Node* n = new Node();
		n->ID = i;
		arr[i] = n;
	}

	for (int i = 0; i < N; i++)
	{
		int ID, IDL, IDR;
		char N, L, R;
		cin >> N >> L >> R;
		ID = (int)N - 'A';
		IDL = (int)L - 'A';
		IDR = (int)R - 'A';
		if (IDL != -19)
			arr[ID]->Left = arr[IDL];
		if (IDR != -19)
			arr[ID]->Right = arr[IDR];
	}
	// 탐색 진행
	preorder(arr[0]);
	cout << '\n';
	inorder(arr[0]);
	cout << '\n';
	postorder(arr[0]);

	return 0;
}

문제 풀이
트리를 순회하는 방식은 크게 3가지가 있습니다. 전위 순회(preorder), 중위순회(inorder), 후위순회(postorser)입니다. 코드를 구현하는 방식은 그리 어렵지 않습니다. 재귀를 이용해서 구현하면 됩니다.

전위 순회
루트-> 왼쪽 자식-> 오른쪽 자식
중위 순회
왼쪽 자식-> 루트-> 오른쪽 자식
후위 순회
왼쪽 자식-> 오른쪽 자식 -> 루트

그리고 구조체를 사용해서 구현하였습니다. 연결 리스트를 구현하는 방식이랑 비슷하다고 생각하면 될 것 같습니다.