1991. 트리 순회

백준 1991번 풀이

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

1991번: 트리 순회

풀이

아이디어

트리 순회 방식이 기억이 안나서 찾아봤기 때문에… 다시는 찾아보지 않고 머릿속에 콱 집어넣어 버리겠다는 의미에서 기록합니다.

재귀로 짜면 되기 때문에 코드 자체는 매우매우 간단했는데 이제 순서가 문제…

✨ 전위순회 (preorder)

순서는 루트 ➡️ 왼쪽 자식(의 자식들) ➡️ 오른쪽 자식(의 자식들)

void preorder(char curr)
{
	if (curr != '.')	// 연결되어 있으면
	{
		// 1. 루트 방문
		cout << curr;
		// 2. 왼쪽 자식을 루트로 하는 전위순회
		preorder(tree[curr - 'A'].first);
		// 3. 오른쪽 자식을 루트로 하는 전위순회
		preorder(tree[curr - 'A'].second);
	}
}

✨ 중위순회 (inorder)

순서는 왼쪽 자식(의 자식들) ➡️ 루트 ➡️ 오른쪽 자식(의 자식들)

void inorder(char curr)
{
	if (curr != '.')
	{
		inorder(tree[curr - 'A'].first);
		cout << curr;
		inorder(tree[curr - 'A'].second);
	}
}

✨ 전위순회 (postorder)

순서는 왼쪽 자식(의 자식들) ➡️ 오른쪽 자식(의 자식들) ➡️ 루트

void postorder(char curr)
{
	if (curr != '.')
	{
		postorder(tree[curr - 'A'].first);
		postorder(tree[curr - 'A'].second);
		cout << curr;
	}
}

코드

// 백준 1991 트리 순회
#include <iostream>
#include <utility>
using namespace std;

int N;
pair<char, char> tree[26];

void input(void)
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	char node, left, right;
	cin >> N;
	for(int i = 0; i < N; i++)
	{
		cin >> node >> left >> right;
		tree[node - 'A'].first = left;
		tree[node - 'A'].second = right;
	}
}

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

void inorder(char curr)
{
	if (curr != '.')
	{
		inorder(tree[curr - 'A'].first);
		cout << curr;
		inorder(tree[curr - 'A'].second);
	}
}

void postorder(char curr)
{
	if (curr != '.')
	{
		postorder(tree[curr - 'A'].first);
		postorder(tree[curr - 'A'].second);
		cout << curr;
	}
}

int main(void)
{
	input();
	preorder('A');
	cout << endl;
	inorder('A');
	cout << endl;
	postorder('A');
	return (0);
}