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

유형	난이도	완료일	링크	특이사항
DFS	실버1	23.4.8	https://www.acmicpc.net/problem/1991

 

 

내 코드

#include <iostream>
#include <vector>

using namespace std;

int n;
int arr[26][26];
char p, c1, c2;
int pk, c1k, c2k;
char output;
vector<int> vec[26];

void Preorder(int node)
{
	output = node+65;
	cout << output;	
	
	if(vec[node][0]!=-1)
		Preorder(vec[node][0]);
	if(vec[node][1]!=-1)
		Preorder(vec[node][1]);

}

void Inorder(int node)
{	
	if(vec[node][0]!=-1)
		Inorder(vec[node][0]);
	
	output = node+65;
	cout << output;
	
	if(vec[node][1]!=-1)
		Inorder(vec[node][1]);	
}

void Postorder(int node)
{	
	if(vec[node][0]!=-1)
		Postorder(vec[node][0]);
	if(vec[node][1]!=-1)
		Postorder(vec[node][1]);

	output = node+65;
	cout << output;	
}

int main(void)
{
	cin >> n;
	for(int i=0; i<n; i++)
	{
		cin >> p >> c1 >> c2;
		
		pk = p-65;
		c1k = c1-65;
		c2k = c2-65;
		
		if(c1k>=0)
		{
			arr[pk][c1k] = 1;
			vec[pk].emplace_back(c1k);
		}
		else
		{
			vec[pk].emplace_back(-1);
		}
		
		if(c2k>=0)
		{
			arr[pk][c2k] = 1;
			vec[pk].emplace_back(c2k);		
		}
		else
		{
			vec[pk].emplace_back(-1);
		}
	}
		
	Preorder(0);
	cout<<"\\n";
	Inorder(0);
	cout<<"\\n";
	Postorder(0);
}

  처음엔 이진트리라는 점을 생각하지 못하고 모든 자식을 26 * 26 배열에 1로 표시하는 방법을 사용했다. 그러나 중위 순회를 구현하기 위해선 자식을 left, right 자식으로 나눌 필요가 있었고 vector를 이용해서 vector[i][0]에는 left child를, vector[i][1]에는 right child를 넣어 트리를 표현했다. 재귀함수로 순회하는 함수를 구현할 수 있으면 쉽게 풀 수 있다.