[백준 5639 C++][S1] 이진 검색 트리

⭐️ 난이도

Silver 1

---

⭐️ 문제

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

5639번: 이진 검색 트리

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하시오.

 

---

⭐️ Idea flow

우선 이 문제에서 노드의 갯수가 몇 개 인지 알려주지 않는다.

따라서 eof를 사용해야 한다. while문으로 수를 계속 받아주다가 eof를 만나면 break를 해준다.

 

전위 순회(preorder)는 root노드를 먼저 방문하는 순회 방법으로서 root -> left child -> right child 순으로 순회를 한다.

root를 기준으로 root보다 작은 수들이 먼저 주어진 다음, root보다 큰 수 들이 주어진다.

 

따라서 전위 순회한 결과를 순서대로 tree에 insert하면 tree를 완성할 수 있다.

 

이후에는 후위 순회(postorder)의 결과를 구해야 한다.

후위 순회(postorder)은 root 노드를 제일 마지막에 방문하는 순회 방법으로서 left child -> right child -> root 순서대로 방문한다.

후위 순회는 재귀적 방법을 통해 구현할 수 있으며, 더 이상 타고 들어갈 자식 노드가 없다면 현재 노드의 key값을 출력해준다.

 

---

⭐️ Code

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>

#define INF 987654321
#define MAX 1000000 + 1
using namespace std;

// 5639 - 이진 검색 트리
template<typename T>
class Node{
public:
    T key;
    Node* left;
    Node* right;

    /*이진 트리에서의 삽입
     * 현재 위치한 노드가 null이라면, Node를 생성하고 key 삽입
     * 만일 삽입하려는 key의 값이 더 크다면, node의 오른쪽 자식으로 이동
     * 만일 삽입하려는 key의 값이 더 작다면, node의 왼쪽 자식으로 이동*/
    Node* insert(Node* node, T _key){
        if(node == nullptr){
            node = new Node<int>;
            node->key = _key;
            node->left = nullptr;
            node->right = nullptr;
        }
        else if(node->key < _key){
            node->right = insert(node->right, _key);
        }
        else{
            node->left = insert(node->left, _key);
        }
        return node;
    }
};

// left -> right -> root
void postOrder(Node<int>* node){
    if(node->left != nullptr){
        postOrder(node->left);
    }
    if(node->right != nullptr){
        postOrder(node->right);
    }
    cout << node->key << '\n';
}


int main(){

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Node<int>* root = nullptr;
    int num = 0;
    while(cin >> num){
        if(num == cin.eof())    break;

        root = root->insert(root, num);
    }
    postOrder(root);

    return 0;
}

 

---

⭐️ Feedback

 

tree 문제를 제대로 풀어본 적이 없는 것 같아 이번에 tree쪽 문제들을 쭉 풀어보려고 한다.

C++ STL에 tree라는 자료구조를 따로 제공하지 않는다.

 

찾아본 바로는 선택지를 대략 두 개로 나눌 수 있는데,

1) 직접 struct를 선언하여 사용 하는 것

   이 방법은 사용자가 직접 구조체를 선언하여 사용하는 방법이다. 사용자의 입맛대로 바꿀 수는 있지만, 모두 구현해야 한다는 번거로움이 있다.

2) STL map을 활용하는 것

   map이 red-black tree 기반이다. binary tree의 일종인데, balance를 맞추어 시간 복잡도를 O(log n)으로 유지시켜준다.

   따라서 이 map 컨테이너를 잘 활용하면 된다고 한다.