이진 트리의 후위 순회
우편 주문 순회 의 유형으로 정의됩니다. 트리 순회 이는 각 노드에 대해 다음과 같은 왼쪽-오른쪽-루트 정책을 따릅니다.
- 왼쪽 하위 트리가 먼저 탐색됩니다.
- 그런 다음 오른쪽 하위 트리를 탐색합니다.
- 마지막으로 하위 트리의 루트 노드를 탐색합니다.
우편 주문 순회
이진 트리의 후위 순회 알고리즘:
후위 순회 알고리즘은 다음과 같습니다.
우편 주문(루트):
- 루트 != NULL이 될 때까지 2~4단계를 따르세요.
- 후위(루트 -> 왼쪽)
- 후위(루트 -> 오른쪽)
- 루트 쓰기 -> 데이터
- 루프 종료
이진 트리의 후위 순회는 어떻게 작동합니까?
다음 트리를 고려해보세요.
이진 트리의 예
이 이진 트리에서 후위 순회를 수행하면 순회는 다음과 같습니다.
1 단계: 순회는 1에서 왼쪽 하위 트리(예: 2)로 이동한 다음 2에서 왼쪽 하위 트리 루트(예: 4)로 이동합니다. 이제 4에는 하위 트리가 없으므로 방문하게 됩니다.
노드 4가 방문되었습니다.
2 단계: 2의 왼쪽 하위 트리를 완전히 방문했으므로 이제 2의 오른쪽 하위 트리를 순회합니다. 즉, 5로 이동합니다. 5의 하위 트리가 없으므로 방문하게 됩니다.
노드 5를 방문했습니다.
3단계: 이제 노드 2의 왼쪽 및 오른쪽 하위 트리를 모두 방문합니다. 이제 노드 2 자체를 방문하십시오.
노드 2가 방문되었습니다.
4단계: 노드 1의 왼쪽 하위 트리를 순회하면 이제 오른쪽 하위 트리 루트, 즉 3으로 이동합니다. 노드 3에는 왼쪽 하위 트리가 없으므로 오른쪽 하위 트리, 즉 6을 순회합니다. 노드 6에는 하위 트리가 없고 그래서 방문합니다.
노드 6을 방문했습니다.
5단계: 노드 3의 모든 하위 트리를 탐색합니다. 이제 노드 3을 방문합니다.
노드 3이 방문됨
6단계: 노드 1의 모든 하위 트리를 순회하므로 이제 노드 1을 방문할 시간이며 그 후 전체 트리를 순회하면서 순회가 종료됩니다.
전체 트리를 방문합니다.
따라서 노드 순회 순서는 다음과 같습니다. 4 -> 5 -> 2 -> 6 -> 3 -> 1 .
이진 트리의 후위 순회를 구현하는 프로그램
다음은 후순위 순회 코드 구현입니다.
C++
// C++ program for postorder traversals> #include> using> namespace> std;> // Structure of a Binary Tree Node> struct> Node {> > int> data;> > struct> Node *left, *right;> > Node(> int> v)> > {> > data = v;> > left = right = NULL;> > }> };> // Function to print postorder traversal> void> printPostorder(> struct> Node* node)> {> > if> (node == NULL)> > return> ;> > // First recur on left subtree> > printPostorder(node->왼쪽);> > // Then recur on right subtree> > printPostorder(node->오른쪽);> > // Now deal with the node> > cout ' '; } // Driver code int main() { struct Node* root = new Node(1); root->왼쪽 = 새 노드(2); 루트->오른쪽 = new Node(3); 루트->왼쪽->왼쪽 = new Node(4); 루트->왼쪽->오른쪽 = new Node(5); 루트->오른쪽->오른쪽 = new Node(6); // 함수 호출 cout < < 'Postorder traversal of binary tree is:
'; printPostorder(root); return 0; }> |
자바
// Java program for postorder traversals> import> java.util.*;> // Structure of a Binary Tree Node> class> Node {> > int> data;> > Node left, right;> > Node(> int> v)> > {> > data = v;> > left = right => null> ;> > }> }> class> GFG {> > > // Function to print postorder traversal> > static> void> printPostorder(Node node)> > {> > if> (node ==> null> )> > return> ;> > // First recur on left subtree> > printPostorder(node.left);> > // Then recur on right subtree> > printPostorder(node.right);> > // Now deal with the node> > System.out.print(node.data +> ' '> );> > }> > // Driver code> > public> static> void> main(String[] args)> > {> > Node root => new> Node(> 1> );> > root.left => new> Node(> 2> );> > root.right => new> Node(> 3> );> > root.left.left => new> Node(> 4> );> > root.left.right => new> Node(> 5> );> > root.right.right => new> Node(> 6> );> > // Function call> > System.out.println(> 'Postorder traversal of binary tree is: '> );> > printPostorder(root);> > }> }> // This code is contributed by prasad264> |
파이썬3
# Python program for postorder traversals> # Structure of a Binary Tree Node> class> Node:> > def> __init__(> self> , v):> > self> .data> => v> > self> .left> => None> > self> .right> => None> # Function to print postorder traversal> def> printPostorder(node):> > if> node> => => None> :> > return> > # First recur on left subtree> > printPostorder(node.left)> > # Then recur on right subtree> > printPostorder(node.right)> > # Now deal with the node> > print> (node.data, end> => ' '> )> # Driver code> if> __name__> => => '__main__'> :> > root> => Node(> 1> )> > root.left> => Node(> 2> )> > root.right> => Node(> 3> )> > root.left.left> => Node(> 4> )> > root.left.right> => Node(> 5> )> > root.right.right> => Node(> 6> )> > # Function call> > print> (> 'Postorder traversal of binary tree is:'> )> > printPostorder(root)> |
씨#
// C# program for postorder traversals> using> System;> // Structure of a Binary Tree Node> public> class> Node {> > public> int> data;> > public> Node left, right;> > public> Node(> int> v)> > {> > data = v;> > left = right => null> ;> > }> }> public> class> GFG {> > // Function to print postorder traversal> > static> void> printPostorder(Node node)> > {> > if> (node ==> null> )> > return> ;> > // First recur on left subtree> > printPostorder(node.left);> > // Then recur on right subtree> > printPostorder(node.right);> > // Now deal with the node> > Console.Write(node.data +> ' '> );> > }> > static> public> void> Main()> > {> > // Code> > Node root => new> Node(1);> > root.left => new> Node(2);> > root.right => new> Node(3);> > root.left.left => new> Node(4);> > root.left.right => new> Node(5);> > root.right.right => new> Node(6);> > // Function call> > Console.WriteLine(> > 'Postorder traversal of binary tree is: '> );> > printPostorder(root);> > }> }> // This code is contributed by karthik.> |
자바스크립트
// Structure of a Binary Tree Node> class Node {> > constructor(v) {> > this> .data = v;> > this> .left => null> ;> > this> .right => null> ;> > }> }> // Function to print postorder traversal> function> printPostorder(node) {> > if> (node ==> null> ) {> > return> ;> > }> > // First recur on left subtree> > printPostorder(node.left);> > // Then recur on right subtree> > printPostorder(node.right);> > // Now deal with the node> > console.log(node.data +> ' '> );> }> // Driver code> function> main() {> > let root => new> Node(1);> > root.left => new> Node(2);> > root.right => new> Node(3);> > root.left.left => new> Node(4);> > root.left.right => new> Node(5);> > root.right.right => new> Node(6);> > // Function call> > console.log(> 'Postorder traversal of binary tree is:
'> );> > printPostorder(root);> }> main();> |
산출
Postorder traversal of binary tree is: 4 5 2 6 3 1
설명:
우편 주문 순회 작동 방식
복잡성 분석:
시간 복잡도: O(N) 여기서 N은 총 노드 수입니다. 왜냐하면 모든 노드를 적어도 한 번은 통과하기 때문입니다.
보조 공간: 재귀 스택 공간을 고려하지 않는 경우 O(1)입니다. 그렇지 않으면, O(h) 여기서 h는 트리의 높이입니다.
- 최악의 경우, 시간 와 같을 수 있다 N (나무가 기울어진 나무인 경우)
- 최선의 경우, 시간 와 같을 수 있다 침착한 (트리가 완전한 트리인 경우)
Postorder Traversal의 사용 사례:
후위순회(postorder traversal)의 일부 사용 사례는 다음과 같습니다.
- 트리 삭제에 사용됩니다.
- 표현식 트리에서 후위 표현식을 가져오는 것도 유용합니다.
관련 기사:
- 트리 순회 유형
- 반복적 후순 순회(스택 2개 사용)
- 반복적 후순 순회(스택 1개 사용)
- 재귀와 스택이 없는 이진 트리의 후위 순서
- 선주문 순회에서 BST의 후순 순회를 찾습니다.
- 우편 주문을 위한 Morris 탐색
- 선주문 및 중순 순회에서 후순 순회 인쇄
