[백준/C++] 트리 순회

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 전위 순회와 후위 순회, 중위 순회의 각 특징만 알면 쉽게 풀 수 있는 문제다.

 

문제에 제시된 출력 순서를 보면 아래와 같다.

• 전위 순회한 결과 : ABDCEFG // (루트) (왼쪽 자식) (오른쪽 자식)
• 중위 순회한 결과 : DBAECFG // (왼쪽 자식) (루트) (오른쪽 자식)
• 후위 순회한 결과 : DBEGFCA // (왼쪽 자식) (오른쪽 자식) (루트)

여기서 전위 순회의 출력 순서를 보면 루트 -> 왼쪽 자식 정점 -> 오른쪽 자식 정점인 모습을 볼 수 있다.

그러므로 pseudo 코드로 표현하면 아래와 같이 표현할 수 있다.

void 전위순회
{
    print(루트노드)
    전위순회(왼쪽 자식 노드)
    전위순회(오른쪽 자식 노드)
}

 

그러면 항상 루트노드를 먼저 출력하고 왼쪽 자식을 전위 순회 하는 코드로 들어간다.

이후 왼쪽 자식의 전위 순회를 마치면 오른쪽 자식을 전위 순회하면서 전위 순회의 경로를 출력하는 코드가 완성된다.

 

 마찬가지로 중위 순회 후위 순회를 아래와 같이 표현할 수 있다.

void 중위 순회
{
    중위순회(왼쪽 자식 노드)
    print(루트노드)
    중위순회(오른쪽 자식 노드)
}

void 후위 순회
{
    후위순회(왼쪽 자식 노드)
    후위순회(오른쪽 자식 노드)
    print(루트노드)
}

 

이러한 수도코드를 만들어 모든 순회 방법을 출력하면 된다.

 

 

​

[아이디어 정리]

1. 노드의 왼쪽 자식과 오른쪽 자식이 어떤 노드인지 저장할 vector를 만드다.
2. 순회를 출력하는 재귀 함수를 만들어 출력한다.

 

 

Code

 

 

#include <iostream>
#include <vector>
using namespace std;

void DFS(vector<pair<int, int>>& childs, int ty, int nowN)
{
	if (ty == 0) //전
	{
		char cc = 'A'+nowN;
		cout << cc;
		if (childs[nowN].first != -1)
			DFS(childs, ty, childs[nowN].first);
		if(childs[nowN].second != -1)
			DFS(childs, ty, childs[nowN].second);
	}
	else if (ty == 1) // 중 
	{
		if (childs[nowN].first != -1)
			DFS(childs, ty, childs[nowN].first);
		char cc = 'A' + nowN;
		cout << cc;
		if (childs[nowN].second != -1)
			DFS(childs, ty, childs[nowN].second);
	}
	else // 후
	{
		if (childs[nowN].first != -1)
			DFS(childs, ty, childs[nowN].first);
		if (childs[nowN].second != -1)
			DFS(childs, ty, childs[nowN].second);
		char cc = 'A' + nowN;
		cout << cc;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	int n;
	cin >> n;
	vector<pair<int, int>> childs(26);
	char a, b, c;
	for (int i = 0; i < n; i++)
	{
		cin >> a >> b >> c;
		if (b == '.')
			childs[a - 'A'].first = -1;
		else
			childs[a - 'A'].first = b - 'A';
		if (c == '.')
			childs[a - 'A'].second = -1;
		else
			childs[a - 'A'].second = c - 'A';
	}
	for (int i = 0; i < 3; i++) {
		DFS(childs, i, 0);
		cout << "\n";
	}
	return 0;
}

 

---

어떻게 보면 하노이 탑 문제와 비슷한 문제였던 것 같다.

재귀와 관련된 문제를 많이 풀어 봤다면 쉽게 풀 수 있는 Well Known...

 

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