boj 1991 - 트리순회(DFS)

PS에서 트리의 자료 구조 저장 방법과 

자료구조의 순회 방법에 대한 문제

 

포인터 기반으로 하여 트리 자료구조를 구현했던 기억이 나는데 PS에서는 동적 할당이

비싸므로 배열을 통한 구현을 전제로 한다. 

 

트리 순회에는

전위 탐색

중위 탐색

후위 탐색이 있으며

 

각각 ROOT를 기준으로 

어느 순서에서 탐색할지를 기준으로 이름을 명명한다.

 

전위탐색은 맨 앞에 ROOT를 탐색하고 다음 왼쪽 오른쪽,

중위 탐색은 왼쪽 다음 중간에 ROOT를 탐색, 그리고 오른쪽

후위 탐색은 왼쪽 오른쪽 자식노드를 먼저 탐색하고 마지막으로 ROOT

 

자료를 저장하는데 있어서는 

해당 문제에서는 이진 트리이므로 각 원소에 대해 pair를 통해 자료를 저장하도록 한다. 

 

탐색 시에는 stack를 쌓는 순서와 출력 순서를 

traversal 순서에 고려하여 배치

 

소스코드

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


void preorder(vector<pair<char,char>> &tree, char index)
{	
	if(index == '.') return;

	const pair<char,char> &root = tree[index-'A'];

	cout<<index;
	preorder(tree, root.first);
	preorder(tree, root.second);
}


void inorder(vector<pair<char,char>> &tree, char index)
{	
	if(index == '.') return;

	pair<char,char> root = tree[index-'A'];

	inorder(tree, root.first);
	cout<<index;
	inorder(tree, root.second);
}


void postorder(vector<pair<char,char>> &tree, char index)
{	
	if(index == '.') return;

	pair<char,char> root = tree[index-'A'];

	postorder(tree, root.first);
	postorder(tree, root.second);
	cout<<index;

}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin>>n;

	vector<pair<char,char>> tree(26);

	for(int i=0; i<n; i++)
	{
		char root;
		char leftnode, rightnode;

		cin>>root>>leftnode>>rightnode;

		tree[root-'A'] = {leftnode,rightnode};
	}

	char index = 'A';
	//전위 순회
	preorder(tree, index);
	cout<<"\n";
	//중위 순회
	inorder(tree, index);
	cout<<"\n";
	//후위 순회
	postorder(tree, index);


}