득이공간

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

PS/알고리즘 문제풀이

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

쟁득 2024. 2. 10. 22:04
 

1991번: 트리 순회

첫째 줄에는 이진 트리의 노드의 개수 N(1 ≤ N ≤ 26)이 주어진다. 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 노드의 이름은 A부터 차례대로 알파

www.acmicpc.net

#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해서

 

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