108. Postorder Traversal

트리의 후위 순회(Postorder Traversal)는 노드의 서브트리를 차례로 방문한 다음 노드를 마지막으로 방문하는 순회 방법이다. 트리의 전위 순회, 중위 순회, 후위 순회 결과 중 두 가지를 알면 나머지 한 가지 순회 결과도 알아낼 수 있다. 앞에서 설명한 트리의 후위 순회 결과는 다음과 같다.

$\text{I F B G A J C H E D}$

 

구현은 다음과 같다.

// 인접 리스트를 사용한 경우

#import<bits/stdc++.h>
using namespace std;
vector<int>v, e[100005];
void postorder_traversal(int prev, int node)
{
    for(auto &p: e[node])if(p != prev)postorder_traversal(p);
    v.push_back(node);
}
int main()
{
    int n, root, x, y;
    cin >> n >> root;
    for(int i = 0; i < n - 1; i++)
    {
        cin >> x >> y;
        e[x].push_back(y);
        e[y].push_back(x);
    }
    postorder_traversal(0, root);
}

// 1번이 루트 노드이고 나머지 노드들의 부모 노드들이 주어진 경우

#import<bits/stdc++.h>
using namespace std;
vector<int>v, e[100005];
void postorder_traversal(int node)
{
    for(auto &p: e[node])postorder_traversal(p);
    v.push_back(node);
}
int main()
{
    int n, x;
    cin >> n;
    for(int i = 2; i <= n; i++)
    {
        cin >> x;
        e[x].push_back(i);
    }
    postorder_traversal(1);
}

---

식을 표현하는 트리를 후위 순회한 결과는 후위 표기식(Postfix Expression)이라고 하며 식을 이 방법으로 나타내는 것을 후위 표기법(Postfix Notation) 또는 역폴란드 표기법(Reverse-Polish Notation, RPN)이라고 한다. 앞에서 설명한 식을 후위 표기식으로 나타내면 다음과 같다.

$$6\ 5+2 \times9\ 3 \div7\ 5+9\ 3-\div\times-$$