백준 1991번 - 트리 순회 (C++ / 트리 순회)

https://www.acmicpc.net/problem/1991

1991번: 트리 순회

문제

이진 트리를 입력받아 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)한 결과를 출력하는 프로그램을 작성하시오.

간단한 트리 순회 문제이다. 트리 구조 짜는것은 각자 편한 방법으로 짜면 될것이고, 여기서 중요한것은 전위,중위,후위 순회를 하는 방법인것 같다. 간단하게 재귀호출을 할때 cout의 위치만 바꿔주면 된다. 

 

접근법

나는 unordered_map을 자식을 연결하기 위해 저장하는 용도로 사용했다. 사실 트리를 순회하면서 노드를 반환해주는 find함수를 구현하면 되지만, 메모리 제한도 넉넉하고, 이진 탐색 트리처럼 정렬되어 있는 트리가 아니라 필요성을 느끼지 못했다.

 

코드

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

struct Node
{
	string data;
	Node* left = nullptr;
	Node* right = nullptr;
};

void inorder(Node* parent)
{
	if (parent == nullptr) return;
	inorder(parent->left);
	if (parent->data != ".")cout << parent->data;
	inorder(parent->right);
}

void preorder(Node* parent)
{
	if (parent == nullptr) return;
	if (parent->data != ".")cout << parent->data;
	preorder(parent->left);
	preorder(parent->right);

}

void postorder(Node* parent)
{
	if (parent == nullptr) return;
	postorder(parent->left);
	postorder(parent->right);
	if (parent->data != ".")cout << parent->data;

}


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

	unordered_map<string, Node*> nodeList;
	Node* parent = new Node();
	
	int N;
	std::cin >> N;
	
	for (int i = 0; i < N; i++)
	{
		string p, r, l;
		Node* left = new Node();
		Node* right = new Node();
		cin >> p >> l >> r;
		if (i == 0)
		{
			parent->data = p;
			parent->left = left;
			parent->right = right;
			nodeList[p] = parent;
		}
		left->data = l;
		right->data = r;
		nodeList[r] = right;
		nodeList[l] = left;
		nodeList[p]->left = left;
		nodeList[p]->right = right;
	}
	preorder(parent);
	std::cout << "\n";
	inorder(parent);
	std::cout << "\n";
	postorder(parent);

}

 

트리를 만들때 i==0일때 최상위 부모만 등록해주는 케이스만 따로 if 문으로 빼주었다.