×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,101,837명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형



http://www.crocus.co.kr/560 이 링크에서는 전위, 후위를 알 때 중위 순회를 구하는 

'트리'를 구하는 소스 코드를 올려두었었다. 


이번에는 트리를 구하지 않고

vector STL을 통해 전위, 중위 순회를 알 때 왼쪽 오른쪽을 계속해서 구분하여 바로 후위 순회를 구하는 소스 코드를 구현하였다.


이 코드의 내용은 '알고리즘 문제 해결 전략 2'에서 확인 할 수 있고,


자세한 내용은 주석을 통해 달아두었다.


이 코드를 가지고 풀 수 있는 문제는 다음과 같다.


[4256번] 트리 :: https://www.acmicpc.net/problem/4256







1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <cstdio>
#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();
 
    // 전제 : 텅 빈 트리면 return;
    if (preorder.empty())
        return;
 
    // 이 트리의 루트는 전위 탐색 결과로부터 알 수 있다.
    const int root = preorder[0];
 
    // 이 트리의 왼쪽 서브트리의 크기는 중위 탐색 결과에서 루트의 위치를 찾아서 알 수 있다.
    int i;
    for (i = 0; i < N; i++)
        if (inorder[i] == root)
            break;
 
    const int L = i;
 
    // 오른쪽 서브 트리의 크기는 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));
 
    // 후위 순회 출력
    printf("%d ", root);
}
int main()
{
    int tCase;
    vector<int> pre;
    vector<int> in;
    scanf("%d"&tCase);
 
    while (tCase--)
    {
        pre.clear();
        in.clear();
 
        int n, val;
        scanf("%d"&n);
 
        for (int i = 1; i <= n; i++)
        {
            scanf("%d"&val);
            pre.push_back(val);
        }
        for (int i = 1; i <= n; i++)
        {
            scanf("%d"&val);
            in.push_back(val);
        }
 
        printPostOrder(pre, in);
 
        printf("\n");
 
    }
 
    return 0;
}
 

//                                                        If you want to see more? click here >>
Crocus



반응형