[Algorithm]Baekjoon 5639번 :: 이진 검색 트리

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

5639번: 이진 검색 트리

struct Node
{
    int num;
    Node* left;
    Node* right;
};
 
Node* insertNode(Node* node, int n)
{
    if (node == nullptr)
    {
        node = new Node({ n,nullptr,nullptr });
    }
 
    else if (n < node->num)
    {
        node->left = insertNode(node->left, n);
    }
 
    else if (n > node->num)
    {
        node->right = insertNode(node->right, n);
    }
 
    return node;
}
 
void postOrder(Node* node)
{
    if (node == nullptr) return;
 
    postOrder(node->left);
    postOrder(node->right);
    printf("%d\n", node->num);
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int input = 0;
 
    Node* root = nullptr;
 
    while (cin >> input)
    {
        root = insertNode(root, input);
    }
 
    postOrder(root);
}

이 문제같은 경우 일단 트리를 만들고, 후위순회를 하는 문제라 생각하고 풀었다.

트리 만드는것도 위처럼 포인터써서 만들던가, 배열로 관리하던가 해서 풀면 된다생각했고, 

일단 두 방식다 코드를 짜봤다.

위처럼 하는건 뭐 무난히 잘 되고, 배열로 하는거는 코드에 문제가 있는것 같진 않은데 틀렸다고 나오길래 생각해보니, 노드갯수가 1000개라서 만약 값이 한쪽으로만 깊게 파여지는 형태가 되어버리면 인덱스번호가 기하급수적으로 늘어나서 배열을 그만큼 크게 잡아줘야 한다.

 

만약 값을 내림차순으로 준다고 생각하면, 깊이가 최대 1000일거고 그러면 최대인덱스번호가 2^1000이 된다....

그래서 이건 불가능하다.

 

다른사람의 풀이를 보니까 전혀 생각치도 못했던 방식이 있었다. 트리를 만들 필요가 없는 코드다.

우리는 전위순회를 한 순서를 입력으로 받는다. (알고 있다는 뜻)

전위순회는 중,왼,오 순서로써, 이 순서를 배열에 그대로 넣고 규칙을 찾아보면 다음과 같는 규칙을 가진다.

 

1. 주어진 구간에서(처음에는 0번째부터 끝까지) 첫번째는 root노드이다.

2.  그다음 root값보다 큰 값을만나기 전까지의 노드들은 전부 왼쪽 서브트리노드들이다. (즉, root노드보다 작은값들)

3. root노드보타 큰값의 인덱스부터, 주어졌던 구간의 마지막까지는 전부 오른쪽 서브트리들이다. (즉, root노드보다 큰 값들)

 

이렇게 왼쪽,오른쪽 서브트리로 나누는게 가능하다!

그러면 이 나눈 구간들에 대해서 또 구간을 나누고 나누다 start 인덱스와 end인덱스가 겹칠 때(구간에 값이 1개만 있을 때)

해당 값을 출력해주면 된다.

후위순회로 출력해야하기 때문에 왼쪽,오른쪽,중간 순서로 재귀를 돌리면 된다.

이건 사실 코드로 보는게 더 이해가 잘된다.

 

vector<int> bt;
 
void postOrder(int start, int end)
{
    if (start >= end + 1) return;
    if (start == end)
    {
        printf("%d\n", bt[start]);
        return;
    }
 
    int index = start + 1;
 
    while (index <= end)
    {
        if (bt[start] < bt[index])
        {
            break;
        }
 
        index++;
    }
 
    postOrder(start + 1, index-1);
    postOrder(index, end);
    printf("%d\n", bt[start]);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int input;
    int index = 0;
 
    while (cin >> input)
    {
        bt.push_back(input);
    }
 
    postOrder(0, bt.size() - 1);
}
 

이 로직을 이해했다면, 이번문제처럼 전위순회결과로 후위순회 결과를 구하는것 뿐만 아니라

그 반대도 가능하다. 중위순회도 충분히 적용 가능할것이다.