[C++] 백준 1991: 트리 순회

문제

[C++] 백준 1991: 트리 순회 SILVER 1
https://www.acmicpc.net/problem/1991

 

---

 

접근 방법

백준 1991번은 이진 트리의 전위, 중위, 후위 순회 결과를 출력하는 문제다.

 

각 노드는 대문자 알파벳으로 표현되고, 입력으로 (부모, 왼쪽 자식, 오른쪽 자식) 형태가 주어진다.
자식이 없는 경우는 '.'로 표시된다.

 

이 문제의 핵심은:

• 트리를 직접 구성하고
• 재귀를 이용해 3가지 순회 방식을 구현하는 것

트리의 노드는 최대 26개(알파벳 A~Z)이므로 배열을 이용해 간단히 표현할 수 있다.

 

처음에 DFS로 푸는 문제라고 생각하여 DFS로 전위순회를 구현했지만 중위순회부터 막혔다..ㅠㅠ

다른 사람들이 푼 걸 보니 너무 간단하게 푸는 문제여서 현타MAX....

 

아래 블로그를 참고하였다.

https://non-stop.tistory.com/119

 

상세 아이디어

1. 트리 저장 방법

pair<char, char> graph[26];

• graph[i].first → 해당 노드의 왼쪽 자식
• graph[i].second → 해당 노드의 오른쪽 자식

노드가 알파벳 문자이므로, 인덱스는 c - 'A'로 변환해서 사용한다.

 

2. 전위 순회 (Preorder)

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

• 현재 노드를 먼저 출력
• 왼쪽 서브트리
• 오른쪽 서브트리

 

3. 중위 순회 (Inorder)

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

 

• 왼쪽 먼저 탐색
• 현재 노드 출력
• 오른쪽 탐색

 

 

3. 후위 순회 (Postorder)

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

• 자식들을 먼저 처리
• 마지막에 현재 노드 출력

 

구현 시 주의할 점

• '.' 처리
  • 자식이 없는 경우 '.'이 들어오므로 재귀 호출 시 반드시  if (c != '.')  조건으로 종료 처리를 해줘야 한다.
• 문자 인덱스 변환
  • graph[c - 'A']처럼 문자를 정수 인덱스로 변환해서 접근해야 한다.
• 루트는 항상 'A'
  • 문제 조건상 루트는 항상 'A'이므로  preorder('A');  부터 시작하면 된다.

 

---

 

코드

#include <iostream>
using namespace std;

int n;
pair<char, char> graph[26];

void preorder(char c)
{
	if (c != '.')
	{
		cout << c;
		preorder(graph[c - 'A'].first);
		preorder(graph[c - 'A'].second);
	}
}
void inorder(char c)
{
	if (c != '.')
	{
		inorder(graph[c - 'A'].first);
		cout << c;
		inorder(graph[c - 'A'].second);
	}
}
void postorder(char c)
{
	if (c != '.')
	{
		postorder(graph[c - 'A'].first);
		postorder(graph[c - 'A'].second);
		cout << c;
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

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

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