108. Postorder Traversal

108. Postorder Traversal

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

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

구현은 다음과 같다.

// 인접 리스트를 사용한 경우 #import using namespace std; vectorv, 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 using namespace std; vectorv, 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-$$

from http://00ad-8e71-00ff-055d.tistory.com/110 by ccl(A) rewrite - 2021-11-17 18:26:40