[백준 C++] 1991 트리 순회 - 이진트리

1991번: 트리 순회

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

string PreorderTree;
string InorderTree;
string PostorderTree;
char Tree[27][2];

void DFS(char Parent)
{
	if (Parent == '.')
	{
		return;
	}

	char LeftChild = Tree[Parent - 65][0];
	char RightChild = Tree[Parent - 65][1];

	PreorderTree.push_back(Parent);
	DFS(LeftChild);
	InorderTree.push_back(Parent);
	DFS(RightChild);
	PostorderTree.push_back(Parent);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int N;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		char Parent, Left, Right;
		cin >> Parent >> Left >> Right;

		Tree[Parent - 65][0] = Left;
		Tree[Parent - 65][1] = Right;
	}

	DFS('A');

	cout << PreorderTree << '\n';
	cout << InorderTree << '\n';
	cout << PostorderTree;
}

---

 

하나의 이진 트리를 전위 순회, 중위 순회, 후위 순회로 각각 출력 연산하도록 하는 문제입니다.

 

순회별 출력 문자를 담을 string을 따로 만들고

깊이우선탐색을 사용해서

 

자식 노드 진입 전에는 전위 순회 문자열에 push,

왼쪽 자식 진입 후에는 중위 순회 문자열에 push,

모든 자식 진입 후에는 후위 순회 문자열에 push해서

 

최종적으로 탐색 순서를 출력하도록 풀었습니다.