[백준] 1991번 트리 순회

 

 

문제

소스코드

#include<iostream>
#include<string_view>

using string_view = std::string_view;

class Node {
private:
public:
	Node() = default;
	Node(const string_view s) :left_(nullptr), right_(nullptr), name_{s.data()}{}
	std::string name_;
	Node* left_;
	Node* right_;
};

class Tree {
private:
	Node* node_;
public:
	Tree()= default;
	Tree(const std::string& s)  {
		node_ = new Node(s);
	}
	
	void SearchRoot(const std::string& root_name, Node* root,Node** result_node) {
		
		if (root == nullptr)
			return;
		
		if (root->name_ == root_name)
			*result_node = root;

		SearchRoot(root_name, root->left_, result_node);
		SearchRoot(root_name, root->right_, result_node);
	}

	void Insert(const string_view root_name, const string_view left_name, const string_view right_name) {

		Node* result_node = nullptr;
		SearchRoot(root_name.data(), node_, &result_node);

		if (result_node != nullptr) {
			Node* newNode = nullptr;
			if (left_name != ".") {
				newNode = new Node(left_name.data());
				result_node->left_ = newNode;
			}
			if (right_name != ".") {
				newNode = new Node(right_name.data());
				result_node->right_ = newNode;
			}
		}
		
	}
	void DisplayAll()const {
		PreOrder(node_);
		std::cout << "\n";
		InOrder(node_);
		std::cout << "\n";
		PostOrder(node_);
		std::cout << "\n";
	}

	//전위 탐색
	void PreOrder(const Node* node)const {
		if (node == nullptr)
			return;
		
		std::cout << node->name_;
		PreOrder(node->left_);
		PreOrder(node->right_);
	}

	//중위 탐색
	void InOrder(const Node* node)const {
		if (node == nullptr)
			return;
		
		InOrder(node->left_);
		std::cout << node->name_;
		InOrder(node->right_);
	}
	//후위 탐색
	void PostOrder(const Node* node)const {
		if (node == nullptr)
			return;

		PostOrder(node->left_);
		PostOrder(node->right_);
		std::cout << node->name_;
	}

};


int main() {
	Tree tree("A");
	int N;
	std::cin >> N;
	std::string root,left,right;

	for (int i = 0; i < N; ++i) {
		std::cin >> root >> left >> right;
		tree.Insert(root, left, right);
	}
	tree.DisplayAll();
}

 

후기

이 문제를 해결하기 위한 키워드는 2가지이다.

 

1. 해당하는 root 노드를 찾아야 한다.

  나는 이 방법을 SearchRoot() 함수를 통해서 해당 노드의 이름이 찾고자 하는 노드이면 매개변수인 이중 포인터를 통해    전달받게 하였다.

 

2. 입력을 완료한 노드를 3가지 방법으로 순회한다.

   이 방법은 트리를 순회는 대표적인 방법인 전위, 중위, 후위를 재귀 함수로 구현해서 출력하게 하였다.

 

* string_view 표준 자료구조를 사용하기 위해 C++ 컴파일러를 17 버전을 사용하였다.

   string_view 자료구조는 기존의 리터럴 문자열을 보다 쉽게 처리하기 위해 생긴 C++17 버전의 자료구조이다.

 

트리를 다시 공부하고 두 달 정도 지난 다음 문제를 풀었는데 아니나 다를까 부분 부분 기억이 안 나서 고생을 했다. 

다른 사람들이 짠 코드를 10~15개를 보았는데 나처럼 포인터를 이용해서 푼 사람보다는 인접 배열을 사용해서 푼 사람이 더 많았다. 대부분 코딩 테스트는 시간제한이 있기 때문에 빠르게 구현하고자 하면 인접 배열의 방법이 가장 좋은 선택이라고 생각한다. 

 

출처 및 레퍼런스

문제 링크:https://www.acmicpc.net/problem/1991

 

관련 자료구조 글

 Tree 이론

이진 검색 트리(Binary Search Tree)