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

#include <iostream>
#include <map>
#include <cstring>

using namespace std;

int n;
map<char, pair<char, char>> nodes;	//노드들을 받아온다.
map<char, bool> visited;	//노드를 갔나의 표시

void FirstCycle(char curr);
void MidCycle(char curr);
void EndCycle(char curr);

void memsetting(int n);

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> n;

	for (int i = 0; i < n; i++)
	{
		char temp1, temp2, temp3;
		cin >> temp1 >> temp2 >> temp3;
		nodes[temp1].first = temp2;
		nodes[temp1].second = temp3;
		visited[temp1] = false;
	}

	FirstCycle('A');
	memsetting(n);
	MidCycle('A');
	memsetting(n);
	EndCycle('A');
}

void FirstCycle(char curr)	// (루트) (왼쪽 자식) (오른쪽 자식)
{
	if (!visited[curr])	//처음부터 순서대로 출력한다.
	{
		cout << curr;
		visited[curr] = true;
	}

	if (nodes[curr].first != '.')	//왼쪽
		FirstCycle(nodes[curr].first);

	if (nodes[curr].second != '.')	//오른쪽
		FirstCycle(nodes[curr].second);
}

void MidCycle(char curr)	// (왼쪽 자식) (루트) (오른쪽 자식)
{
	if (nodes[curr].first != '.')	//왼쪽을 계속 들어갔다가
		MidCycle(nodes[curr].first);

	if (!visited[curr])	//나오면서 하나씩 출력
	{
		cout << curr;
		visited[curr] = true;
	}

	if (nodes[curr].second != '.')	//나오는데 오른쪽 자식이 있으면 들어간다.
		MidCycle(nodes[curr].second);

	if (!visited[curr])	//나오면서 하나씩 출력
	{
		cout << curr;
		visited[curr] = true;
	}
}
void EndCycle(char curr)	// (왼쪽 자식) (오른쪽 자식) (루트)
{
	if (nodes[curr].first != '.')	//왼쪽 쭉 들어간다
		EndCycle(nodes[curr].first);

	//b에서 a로 다시 돌아와도 오른쪽이 남았기때문에 출력 못하여 맨 나중에 출력하게 됨
	if (nodes[curr].second != '.')	//왼쪽이 다 들어가고 오른쪽 쭉 들어간다
		EndCycle(nodes[curr].second);

	if (!visited[curr])	//끝쪽이면 출력
	{
		cout << curr;
		visited[curr] = true;
	}

}

void memsetting(int n)	//memset를 어떻게 쓸지 애매하여 직접 false로
{
	char A = 'A';
	for (int i = 0; i < n; i++)
	{
		visited[A] = false;
		A++;
	}
	cout << "\n";
}

 

 

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

현재 노드에서 왼쪽 오른쪽을 두어 탐색한다.