Algospot TRAVERSAL

문제 링크입니다: https://algospot.com/judge/problem/read/TRAVERSAL

소스코드에 앞서서 전위 순회(Preorder Traversal), 중위 순회(Inorder Traversal), 후위 순회(Postorder Traversal)의 Pseudo Code를 간단히 소개하겠습니다.

전위 순회

if (currentNode)

{

        Visit(currentNode);

        Preorder(currentNode->leftChild);

        Preorder(currentNode->rightChild);

}

중위 순회

if (currentNode)

{

        Inorder(currentNode->leftChild);

        Visit(currentNode);

        Inorder(currentNode->rightChild);

}

후위 순회

if (currentNode)

{

        Postorder(currentNode->leftChild);

        Postorder(currentNode->rightChild);

        Visit(currentNode);

}

코드를 보면 알 수 있다 싶이, 전위 순회는 루트를 먼저 방문한 다음에 왼쪽과 오른쪽 서브트리를 순서대로 방문합니다.

중위 순회는 왼쪽 서브트리를 방문한 뒤, 루트를 방문하고 마지막에 오른쪽 서브트리를 방문합니다.

후위 순회는 왼쪽 서브트리, 오른쪽 서브트리를 방문한 다음에 마지막에 루트를 방문합니다.

따라서, 후위 순회에서는 루트가 가장 마지막에 출력되어야 합니다!

전위 순회와 중위 순회의 순서가 주어질 때, 왼쪽 서브트리와 오른쪽 서브트리를 파악해야 후위 순회를 올바르게 출력할 수 있습니다.

루트의 위치가 L이라면 전위 순회의 왼쪽 서브트리는 1~(L+1) 이고 (0이 루트이기 때문에), 중위 순회의 왼쪽 서브트리는 0~L입니다.

마찬가지로 전위 순회의 오른쪽 서브트리는 (L+1)~N이고 중위 순회의 오른쪽 서브트리는 (L+1)~N입니다.(L이 루트의 위치이기 때문에)

#include <iostream>

#include <string>

#include <algorithm>

#include <vector>

using namespace std;

 

vector<int> slice(const vector<int> &v, int a, int b)

{

        return vector<int>(v.begin() + a, v.begin() + b);

}

 

//트리의 전위탐색 결과와 중위탐색 결과가 주어질 때 후위 탐색 결과를 출력한다

void printPostOrder(const vector<int> &preorder, const vector<int> &inorder)

{

        //트리에 포함된 노드의 수

        const int N = preorder.size();

        //기저 사례: 텅 빈 트리면 곧장 종료

        if (preorder.empty())

                 return;

        //이 트리의 루트는 전위 탐색 결과로부터 곧장 알 수 있다

        const int root = preorder[0];

        //이 트리의 왼쪽 서브트리의 크기는 중위 탐색 결과에서 루트의 위치를 찾아서 알 수 있다

        const int L = find(inorder.begin(), inorder.end(), root) - inorder.begin();

        //오른쪽 서브트리의 크기는 N에서 왼쪽 서브트리와 루트를 빼면 알 수 있다

        const int R = N - L - 1;

        //왼쪽 서브트리의 순회 결과를 출력

        printPostOrder(slice(preorder, 1, L + 1), slice(inorder, 0, L));

        //오른쪽 서브트리의 순회 결과를 출력

        printPostOrder(slice(preorder, L + 1, N), slice(inorder, L + 1, N));

        //후위 순회이므로 루트를 가장 마지막에 출력

        cout << root << " ";

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

 

        for (int i = 0; i < test_case; i++)

        {

                 int N;

                 cin >> N;

 

                 vector<int> preorder, inorder;

 

                 for (int i = 0; i < N; i++)

                 {

                         int node;

                         cin >> node;

                         preorder.push_back(node);

                 }

                 for (int i = 0; i < N; i++)

                 {

                         int node;

                         cin >> node;

                         inorder.push_back(node);

                 }

 

                 printPostOrder(preorder, inorder);

                 cout << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략