3.7.3 Post-Order Traversal

CS - 3. Common Algorithms - 3.7 Tree - 3.7.3 Post-Order Traversal

Post-Order Traversal

💡Post-order traversal is a type of tree traversal that visits the left subtree, then the right subtree, and finally the root node. This is the opposite of pre-order traversal, which visits the root node first, then the left subtree, and finally the right subtree.

후위 순은 트리의 일종으로 왼쪽 부분 트리, 오른쪽 부분 트리, 그리고 마지막으로 루트 노드를 방문합니다. 이것은 루트 노드를 먼저 방문하고 왼쪽 부분 트리, 그리고 마지막으로 오른쪽 부분 트리를 방문하는 전위 순회와 반대입니다.

 

이진 트리에서의 순회 방법 중 하나인 Post-Order Traversal은 이름 그대로 '후위 순회'를 의미합니다. 이 방법은 노드를 다음과 같은 순서로 방문합니다
왼쪽 하위 트리 -> 오른쪽 하위 트리 -> 루트 노드. 이 순서대로 방문하게 되면, 노드의 값들이 '후위' 순서로 나타나게 됩니다.

 

In Python

 

Post-Order Traversal을 구현해보겠습니다.

class Node:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

def printPostorder(root):
    if root:
        printPostorder(root.left)
        printPostorder(root.right)
        print(root.val)

 

후위 순회 vs 중위 순회

정의에따라 순서만 바꿔주면 된다.

 

 

후위 순회의 정의에 따라서 어떤 절차에 의해서 결과가 나왔는지 알아보자.

 

1. 처음에는 루트 노드인 1에서 시작합니다. 하지만 Post-Order Traversal은 루트 노드를 가장 마지막에 방문하므로, 먼저 왼쪽 하위 트리인 2를 방문합니다.
2. 노드 2에서 또 다시 Post-Order Traversal을 수행하게 됩니다. 왼쪽 하위 트리인 4를 먼저 방문하고, 이 노드는 더 이상 하위 노드가 없으므로 바로 출력합니다. (4)
3. 그 다음 오른쪽 하위 트리인 5를 방문하고, 이 노드 역시 하위 노드가 없으므로 바로 출력합니다. (4, 5)
4. 이제 노드 2의 왼쪽 하위 트리와 오른쪽 하위 트리를 모두 방문했으므로, 노드 2를 출력합니다. (4,5,2)
5. 이제 루트 노드 1의 왼쪽 하위 트리를 모두 방문했으므로, 오른쪽 하위 트리인 3을 방문합니다. (4,5,2)
6. 노드 3에서 또 다시 Post-Order Traversal을 수행하게 됩니다. 왼쪽 하위 트리인 6을 먼저 방문하고, 이 노드는 더 이상 하위 노드가 없으므로 바로 출력합니다. (4,5,2,6)
7. 그 다음 오른쪽 하위 트리인 7을 방문하고, 이 노드 역시 하위 노드가 없으므로 바로 출력합니다. (4,5,2,6,7)
8. 이제 노드 3의 왼쪽 하위 트리와 오른쪽 하위 트리를 모두 방문했으므로, 노드 3을 출력합니다. (4,5,2,6,7,3)
9. 마지막으로, 루트 노드 1의 왼쪽 하위 트리와 오른쪽 하위 트리를 모두 방문했으므로, 루트 노드 1을 출력합니다.

(4,5,2,6,7,3,1)