Postorder Traversal

후위 순회(Postorder Traversal)

후위 순회(Postorder Traversal)는 트리 자료구조를 탐색하는 세 가지 기본적인 방법(전위, 중위, 후위) 중 하나로, 특별한 방문 순서와 특성을 가지고 있다.

후위 순회는 자식 노드를 먼저 방문한 후 부모 노드를 방문하는 트리 순회 방법으로, 상향식 처리가 필요한 다양한 문제 해결에 적합하다.
트리 삭제, 표현식 평가, 디렉토리 크기 계산과 같은 작업에서 후위 순회의 특성이 자연스럽게 활용된다.

재귀적 구현이 가장 직관적이지만, 스택을 사용한 반복적 구현이나 모리스 순회와 같은 고급 기법을 통해 성능과 공간 효율성을 개선할 수 있다. 각 구현 방법은 상황에 따라 장단점이 있으므로, 문제의 성격과 제약 조건을 고려하여 적절한 방법을 선택해야 한다.

후위 순회의 기본 개념

후위 순회는 이진 트리를 탐색할 때 다음과 같은 순서로 노드를 방문하는 방법이다:

1. 왼쪽 서브트리를 후위 순회한다.
2. 오른쪽 서브트리를 후위 순회한다.
3. 현재 노드(루트)를 방문한다.

“후위(Postorder)“라는 이름은 현재 노드가 왼쪽과 오른쪽 서브트리를 방문한 “후(post)“에 방문된다는 의미를 담고 있다. 이 순회 방식도 깊이 우선 탐색(DFS)의 한 형태로, 트리의 가장 깊은 레벨부터 처리하여 상위 노드로 올라가는 상향식(bottom-up) 접근법을 취한다.

후위 순회의 알고리즘

아래 이진 트리를 예로 들어 후위 순회 과정을 단계별로 살펴보자:

1
2
3
4
5

       1
     /   \
    2     3
   / \   / \
  4   5 6   7

후위 순회 순서: 4 → 5 → 2 → 6 → 7 → 3 → 1

이 순서를 단계별로 설명하면:

1. 가장 왼쪽 경로를 따라 내려가 노드 4에 도달하고 방문한다 (왼쪽, 오른쪽 자식이 없음).
2. 노드 4의 부모인 노드 2의 오른쪽 자식인 노드 5로 이동하여 방문한다.
3. 노드 5의 왼쪽, 오른쪽 자식을 모두 방문했으므로(또는 자식이 없으므로), 노드 2를 방문한다.
4. 노드 2의 부모인 노드 1의 오른쪽 자식인 노드 3으로 이동한다.
5. 노드 3의 왼쪽 자식인 노드 6을 방문한다.
6. 노드 3의 오른쪽 자식인 노드 7을 방문한다.
7. 노드 6과 7을 모두 방문했으므로, 노드 3을 방문한다.
8. 마지막으로, 모든 자식(노드 2와 3)을 방문했으므로 루트 노드 1을 방문한다.

1
2
3
4
5

        A
       / \
      B   C
     / \   \
    D   E   F

후위 순회(Postorder Traversal)의 과정은 다음과 같다.

1. D 방문 (B의 왼쪽 자식) → 출력: D
2. E 방문 (B의 오른쪽 자식) → 출력: D E
3. B 방문 (B의 루트) → 출력: D E B
4. F 방문 (C의 오른쪽 자식) → 출력: D E B F
5. C 방문 (C의 루트) → 출력: D E B F C
6. A 방문 (A의 루트) → 출력: D E B F C A

재귀적 구현

후위 순회의 재귀적 구현은 직관적이고 간결하다:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def postorder_traversal(node):
    if node is None:
        return
    
    # 1. 왼쪽 서브트리 순회
    postorder_traversal(node.left)
    
    # 2. 오른쪽 서브트리 순회
    postorder_traversal(node.right)
    
    # 3. 현재 노드 방문
    print(node.value)

후위 순회의 재귀적 성질은 “자식 노드를 먼저 처리한 후에 부모 노드를 처리한다"는 점에서 많은 문제 해결에 유용하다.

반복적(비재귀적) 구현

후위 순회의 반복적 구현은 전위나 중위 순회보다 조금 더 복잡하다. 두 개의 스택을 사용하거나, 노드의 방문 상태를 추적해야 한다:

두 개의 스택을 사용한 방법

 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

def postorder_traversal_iterative(root):
    if root is None:
        return []
    
    result = []
    stack1 = [root]
    stack2 = []
    
    # 첫 번째 스택에서 노드를 꺼내 두 번째 스택에 넣음
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        
        # 전위 순회의 반대 순서로 자식 노드를 첫 번째 스택에 추가
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    
    # 두 번째 스택에서 노드를 꺼내서 결과에 추가
    while stack2:
        node = stack2.pop()
        result.append(node.value)
    
    return result

방문 상태를 추적하는 방법

 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

def postorder_traversal_iterative_single_stack(root):
    if root is None:
        return []
    
    result = []
    stack = []
    current = root
    last_visited = None
    
    while current or stack:
        # 왼쪽 경로의 모든 노드를 스택에 추가
        while current:
            stack.append(current)
            current = current.left
        
        # 스택의 맨 위 노드 확인
        peek = stack[-1]
        
        # 오른쪽 자식이 없거나 이미 방문했으면 현재 노드 방문
        if not peek.right or peek.right == last_visited:
            result.append(peek.value)
            last_visited = stack.pop()
            current = None
        else:
            # 오른쪽 자식으로 이동
            current = peek.right
    
    return result

이 방법은 노드의 왼쪽 자식과 오른쪽 자식이 모두 방문되었는지 확인한 후에만 노드를 방문한다.

다양한 트리 구조에서의 후위 순회

1. 이진 검색 트리(Binary Search Tree)
   이진 검색 트리에서 후위 순회는 하위 트리부터 처리하는 특성이 있어, 트리 삭제와 같은 작업에 유용하다.

   1 2 3 4 5 6 7

   8 / \ 3 10 / \ \ 1 6 14 / \ / 4 7 13

   후위 순회 순서: 1 → 4 → 7 → 6 → 3 → 13 → 14 → 10 → 8

2. 편향 트리(Skewed Tree)
   한쪽으로만 자식 노드가 있는 트리이다.

   왼쪽 편향 트리:

   1 2 3 4 5 6 7

   1 / 2 / 3 / 4

   후위 순회 순서: 4 → 3 → 2 → 1

   오른쪽 편향 트리:

   1 2 3 4 5 6 7

   1 \ 2 \ 3 \ 4

   후위 순회 순서: 4 → 3 → 2 → 1

   후위 순회에서는 편향 트리의 방향에 관계없이 항상 리프 노드부터 루트 노드까지 아래에서 위로 방문한다.

3. 완전 이진 트리(Complete Binary Tree)
   완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨의 노드들은 왼쪽부터 채워진 트리이다.

   1 2 3 4 5

   1 / \ 2 3 / \ / 4 5 6

   후위 순회 순서: 4 → 5 → 2 → 6 → 3 → 1

4. 일반 트리(N-ary Tree)
   각 노드가 0개 이상의 자식 노드를 가질 수 있는 트리이다.

   1 2 3 4 5

   1 / | \ 2 3 4 /\ | /\ 5 6 7 8 9

   일반 트리에서의 후위 순회:

   1. 각 자식 노드를 왼쪽에서 오른쪽 순서로 후위 순회합니다.
   2. 현재 노드를 방문합니다.

   후위 순회 순서: 5 → 6 → 2 → 7 → 3 → 8 → 9 → 4 → 1

후위 순회의 활용 사례

1. 트리 삭제(Tree Deletion)
   후위 순회는 트리를 삭제할 때 자연스러운 방법이다.
   자식 노드를 먼저 삭제한 후에 부모 노드를 삭제하는 방식이기 때문에 메모리 관리 측면에서 효율적이다.

   1 2 3 4 5 6 7 8 9 10 11 12 13

   def delete_tree(node): if node is None: return # 왼쪽 서브트리 삭제 delete_tree(node.left) # 오른쪽 서브트리 삭제 delete_tree(node.right) # 현재 노드 삭제 print(f"노드 {node.value} 삭제") del node

2. 디렉토리 크기 계산
   파일 시스템에서 디렉토리의 총 크기를 계산할 때 후위 순회가 유용하다. 각 하위 디렉토리와 파일의 크기를 먼저 계산한 후, 현재 디렉토리의 크기를 구할 수 있다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   def calculate_directory_size(path): if os.path.isfile(path): return os.path.getsize(path) total_size = 0 # 하위 항목의 크기 계산 for item in os.listdir(path): item_path = os.path.join(path, item) total_size += calculate_directory_size(item_path) # 현재 디렉토리 자체의 크기 추가 (메타데이터 등) total_size += os.path.getsize(path) print(f"디렉토리 {path}의 크기: {total_size} 바이트") return total_size

3. 표현식 트리의 후위 표기법(Postfix Notation) 변환
   표현식 트리에서 후위 순회를 수행하면 후위 표기법(postfix notation 또는 Reverse Polish notation)의 수식을 얻을 수 있다.

   예를 들어, 중위 표기법 a + b * c를 표현하는 트리는 다음과 같습니다:

   1 2 3 4 5

   + / \ a * / \ b c

   후위 순회를 수행하면 a b c * +라는 후위 표기법을 얻을 수 있다.
   후위 표기법은 스택을 사용하여 효율적으로 계산할 수 있으며, 괄호가 필요 없다는 장점이 있다.

4. 표현식 트리 평가(Expression Tree Evaluation)
   후위 순회는 표현식 트리를 평가(계산)하는 데 자연스럽게 사용된다.
   왼쪽과 오른쪽 서브트리를 먼저 평가한 후, 현재 노드의 연산자를 적용한다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

   def evaluate_expression_tree(node): if node is None: return 0 # 리프 노드는 숫자를 나타냄 if not node.left and not node.right: return node.value # 왼쪽 서브트리 평가 left_value = evaluate_expression_tree(node.left) # 오른쪽 서브트리 평가 right_value = evaluate_expression_tree(node.right) # 현재 노드의 연산자 적용 if node.value == '+': return left_value + right_value elif node.value == '-': return left_value - right_value elif node.value == '*': return left_value * right_value elif node.value == '/': return left_value / right_value

5. 이진 트리의 깊이 계산
   후위 순회를 사용하여 이진 트리의 깊이(또는 높이)를 계산할 수 있다.
   왼쪽과 오른쪽 서브트리의 깊이를 먼저 계산한 후, 더 큰 값에 1을 더하면 현재 노드를 루트로 하는 서브트리의 깊이가 된다.

   1 2 3 4 5 6 7 8 9 10 11 12

   def calculate_tree_depth(node): if node is None: return 0 # 왼쪽 서브트리의 깊이 계산 left_depth = calculate_tree_depth(node.left) # 오른쪽 서브트리의 깊이 계산 right_depth = calculate_tree_depth(node.right) # 더 깊은 서브트리의 깊이 + 1 반환 return max(left_depth, right_depth) + 1

후위 순회의 시간 및 공간 복잡도

1. 시간 복잡도
   후위 순회는 트리의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(n)이다. 여기서 n은 트리의 노드 수이다.

2. 공간 복잡도

   • 재귀적 구현: 재귀 호출 스택의 크기는 트리의 높이 h에 비례하므로 공간 복잡도는 O(h)이다. 최악의 경우(편향 트리)에는 O(n)이 될 수 있다.
   • 반복적 구현(두 개의 스택): 두 개의 스택을 사용하는 경우 공간 복잡도는 O(n)이다.
   • 반복적 구현(한 개의 스택): 한 개의 스택과 방문 상태를 추적하는 경우 공간 복잡도는 O(h)이다. 최악의 경우에는 O(n)이 될 수 있다.

후위 순회와 다른 순회 방법 비교

1. 후위 순회 vs 전위 순회(Preorder Traversal)

   • 후위 순회: 왼쪽 → 오른쪽 → 루트
   • 전위 순회: 루트 → 왼쪽 → 오른쪽
     전위 순회는 루트 노드를 먼저 방문하므로 트리의 복제나 전위 표기법 생성에 유용하다.
     반면 후위 순회는 리프 노드부터 시작하여 트리 삭제나 후위 표기법 생성에 적합하다.

2. 후위 순회 vs 중위 순회(Inorder Traversal)

   • 후위 순회: 왼쪽 → 오른쪽 → 루트
   • 중위 순회: 왼쪽 → 루트 → 오른쪽
     중위 순회는 이진 검색 트리에서 노드를 오름차순으로 방문할 때 유용하다.
     후위 순회는 모든 자식 노드를 처리한 후 부모 노드를 처리하므로 상향식 계산에 적합하다.

3. 후위 순회의 상향식 처리의 장점
   후위 순회의 가장 큰 특징은 자식 노드를 먼저 처리한 후 부모 노드를 처리하는 상향식(bottom-up) 접근법이다.
   이는 다음과 같은 장점이 있다:

   1. 트리 삭제 시 메모리 누수 방지
   2. 디렉토리 크기 계산과 같은 집계 연산에 효율적
   3. 표현식 트리 평가에 자연스러운 방법 제공
   4. 후위 표기법 생성에 적합

실제 코드 예제: 이진 트리의 후위 순회 구현

아래는 Python으로 이진 트리 노드 클래스와 후위 순회 메서드를 구현한 예제:

 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

class TreeNode:
    def __init__(self, value=0, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

def postorder_traversal_recursive(root):
    result = []
    
    def dfs(node):
        if not node:
            return
        
        # 왼쪽 서브트리 순회
        dfs(node.left)
        
        # 오른쪽 서브트리 순회
        dfs(node.right)
        
        # 현재 노드 방문
        result.append(node.value)
    
    dfs(root)
    return result

def postorder_traversal_iterative_two_stacks(root):
    if not root:
        return []
    
    result = []
    stack1 = [root]
    stack2 = []
    
    while stack1:
        node = stack1.pop()
        stack2.append(node)
        
        if node.left:
            stack1.append(node.left)
        if node.right:
            stack1.append(node.right)
    
    while stack2:
        node = stack2.pop()
        result.append(node.value)
    
    return result

# 다음과 같은 이진 트리 생성:
#       1
#     /   \
#    2     3
#   / \   / \
#  4   5 6   7
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
root.left.right = TreeNode(5)
root.right.left = TreeNode(6)
root.right.right = TreeNode(7)

# 재귀적 방법으로 후위 순회
print("재귀적 후위 순회:", postorder_traversal_recursive(root))  # [4, 5, 2, 6, 7, 3, 1]

# 반복적 방법으로 후위 순회 (두 개의 스택 사용)
print("반복적 후위 순회 (두 개의 스택):", postorder_traversal_iterative_two_stacks(root))  # [4, 5, 2, 6, 7, 3, 1]

후위 순회의 응용 문제

1. 이진 트리의 최대 경로 합(Maximum Path Sum)
   이진 트리에서 임의의 두 노드 사이의 경로 중 노드 값의 합이 가장 큰 경로를 찾는 문제.
   후위 순회를 사용하면 각 서브트리의 최대 경로 합을 계산할 수 있다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

   def max_path_sum(root): max_sum = [float('-inf')] # 최대 경로 합을 저장할 리스트 (전역 변수 대신 사용) def postorder(node): if not node: return 0 # 왼쪽 서브트리의 최대 합 계산 (음수면 0으로 처리) left_sum = max(0, postorder(node.left)) # 오른쪽 서브트리의 최대 합 계산 (음수면 0으로 처리) right_sum = max(0, postorder(node.right)) # 현재 노드를 포함하는 경로의 최대 합 갱신 max_sum[0] = max(max_sum[0], node.value + left_sum + right_sum) # 상위 경로에 기여할 수 있는 최대 합 반환 (현재 노드 + 왼쪽 또는 오른쪽 중 더 큰 값) return node.value + max(left_sum, right_sum) postorder(root) return max_sum[0]

2. 이진 트리의 직렬화 및 역직렬화(Serialization and Deserialization)
   이진 트리를 문자열로 변환하는 직렬화와 그 문자열로부터 원래 트리를 복원하는 역직렬화 과정에서 후위 순회를 활용할 수 있다.

   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

   def serialize(root): """이진 트리를 후위 순회 방식으로 직렬화합니다.""" if not root: return "null," # 왼쪽 서브트리 직렬화 left_serialized = serialize(root.left) # 오른쪽 서브트리 직렬화 right_serialized = serialize(root.right) # 현재 노드의 값을 추가 return left_serialized + right_serialized + str(root.value) + "," def deserialize(data): """후위 순회 방식으로 직렬화된 문자열에서 이진 트리를 복원합니다.""" def build_tree(tokens): value = tokens.pop() if value == "null": return None node = TreeNode(int(value)) # 후위 순회에서는 오른쪽 서브트리가 먼저 나옴 node.right = build_tree(tokens) node.left = build_tree(tokens) return node tokens = data.split(",") tokens = [token for token in tokens if token] # 빈 문자열 제거 tokens.pop() # 마지막 쉼표로 인한 빈 토큰 제거 return build_tree(tokens)

3. 이진 트리의 후위 순회 검증(Validate Postorder Sequence)
   주어진 정수 배열이 이진 검색 트리의 유효한 후위 순회 결과인지 확인하는 문제.

   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

   def verify_postorder(postorder): """ 이진 검색 트리의 후위 순회 결과가 유효한지 확인합니다. """ if not postorder: return True root_value = postorder[-1] # 후위 순회의 마지막 값은 루트 # 왼쪽 서브트리와 오른쪽 서브트리의 경계 찾기 i = 0 while i < len(postorder) - 1 and postorder[i] < root_value: i += 1 # 오른쪽 서브트리의 모든 값이 루트보다 커야 함 for j in range(i, len(postorder) - 1): if postorder[j] < root_value: return False # 왼쪽 서브트리와 오른쪽 서브트리 각각 검증 left_valid = True if i > 0: left_valid = verify_postorder(postorder[:i]) right_valid = True if i < len(postorder) - 1: right_valid = verify_postorder(postorder[i:-1]) return left_valid and right_valid

후위 순회의 고급 응용

1. 트리의 최소 공통 조상(Lowest Common Ancestor) 찾기
   두 노드의 최소 공통 조상(LCA)을 찾는 문제는 후위 순회를 사용하여 효율적으로 해결할 수 있다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   def lowest_common_ancestor(root, p, q): if not root or root == p or root == q: return root # 왼쪽 서브트리에서 p 또는 q 찾기 left = lowest_common_ancestor(root.left, p, q) # 오른쪽 서브트리에서 p 또는 q 찾기 right = lowest_common_ancestor(root.right, p, q) # 왼쪽과 오른쪽 서브트리에서 각각 하나씩 찾았다면, 현재 노드가 LCA if left and right: return root # 왼쪽 또는 오른쪽 서브트리에서만 찾았다면, 그 서브트리에 LCA가 있음 return left if left else right

2. 트리의 직경(Diameter) 계산
   트리의 직경은 트리에서 가장 먼 두 노드 사이의 경로 길이이다.
   후위 순회를 사용하여 각 노드를 루트로 하는 서브트리의 높이를 계산하면서 직경을 구할 수 있다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

   def diameter_of_binary_tree(root): diameter = [0] # 최대 직경을 저장할 리스트 def height(node): if not node: return 0 # 왼쪽 서브트리의 높이 left_height = height(node.left) # 오른쪽 서브트리의 높이 right_height = height(node.right) # 현재 노드를 지나는 경로의 길이로 직경 갱신 diameter[0] = max(diameter[0], left_height + right_height) # 현재 노드를 루트로 하는 서브트리의 높이 반환 return max(left_height, right_height) + 1 height(root) return diameter[0]

3. 이진 트리의 모든 경로 출력
   루트에서 리프까지의 모든 경로를 출력하는 문제도 후위 순회의 변형을 사용하여 해결할 수 있다.

   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

   def binary_tree_paths(root): if not root: return [] paths = [] def dfs(node, path): # 현재 노드를 경로에 추가 path.append(str(node.value)) # 리프 노드에 도달하면 경로를 결과에 추가 if not node.left and not node.right: paths.append("->".join(path)) path.pop() # 백트래킹 return # 왼쪽 서브트리 탐색 if node.left: dfs(node.left, path) # 오른쪽 서브트리 탐색 if node.right: dfs(node.right, path) # 현재 경로에서 노드 제거 (백트래킹) path.pop() dfs(root, []) return paths

   이 함수는 전위 순회와 백트래킹을 결합하여 모든 경로를 찾는다. 후위 순회의 특성인 “자식 노드를 모두 처리한 후 부모 노드 처리"는 백트래킹 단계(path.pop())에서 활용된다.

4. 후위 순회를 이용한 이진 트리 구조 검증
   이진 트리가 특정 구조적 속성을 만족하는지 확인하는 데 후위 순회가 유용한다.
   예를 들어, 이진 트리가 균형 잡혀 있는지 확인하는 문제를 살펴보면:

   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

   def is_balanced(root): """ 이진 트리가 균형 잡혀 있는지 확인합니다. 균형 잡힌 트리란 모든 노드에서 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하인 트리입니다. """ def check_height(node): if not node: return 0 # 왼쪽 서브트리의 높이 확인 left_height = check_height(node.left) if left_height == -1: return -1 # 이미 불균형이 발견됨 # 오른쪽 서브트리의 높이 확인 right_height = check_height(node.right) if right_height == -1: return -1 # 이미 불균형이 발견됨 # 현재 노드에서 높이 차이 확인 if abs(left_height - right_height) > 1: return -1 # 불균형 발견 # 현재 노드를 루트로 하는 서브트리의 높이 반환 return max(left_height, right_height) + 1 return check_height(root) != -1

   이 알고리즘은 트리의 높이를 계산하면서 동시에 균형 조건을 검사한다. 후위 순회의 상향식 접근법이 이 작업에 매우 적합하다.

트리 순회의 실제 응용 사례

1. 컴파일러 설계에서의 후위 순회
   컴파일러에서 추상 구문 트리(AST)를 처리할 때 후위 순회가 중요한 역할을 한다.
   표현식을 계산하거나 코드를 생성할 때, 자식 노드(피연산자 또는 하위 표현식)를 먼저 처리한 후 부모 노드(연산자 또는 상위 표현식)를 처리하는 방식을 사용한다.

   예를 들어, 다음과 같은 C 언어 표현식이 있다고 가정해보면:

   1	a = b + c * d;

   이 표현식의 AST는 다음과 같을 수 있다:

   1 2 3 4 5 6 7

   = / \ a + / \ b * / \ c d

   후위 순회 순서: a → b → c → d → * → + → =

   컴파일러는 이 순서대로 코드를 생성할 수 있다:

   1. 변수 a에 접근
   2. 변수 b에 접근
   3. 변수 c에 접근
   4. 변수 d에 접근
   5. c와 d를 곱하기
   6. b와 (c*d)의 결과를 더하기
   7. a에 (b+(c*d))의 결과를 할당

2. 게임 AI에서의 미니맥스 알고리즘(Minimax Algorithm)
   체스, 오델로, 틱택토와 같은 게임의 AI에서는 미니맥스 알고리즘이 사용되는데, 이 알고리즘은 게임 트리를 후위 순회하는 방식으로 동작한다.
   리프 노드(게임의 종료 상태)의 값을 평가한 후, 그 값을 상위 노드로 전파한다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   def minimax(node, depth, is_maximizing_player): # 리프 노드에 도달하거나 게임이 종료된 경우 if depth == 0 or node.is_terminal(): return node.evaluate() if is_maximizing_player: value = float('-inf') for child in node.get_children(): value = max(value, minimax(child, depth - 1, False)) return value else: value = float('inf') for child in node.get_children(): value = min(value, minimax(child, depth - 1, True)) return value

   이 알고리즘은 게임 트리의 리프 노드부터 시작하여 각 레벨에서 최선의 선택을 결정해 나가는 상향식 접근법을 사용한다.

3. 네트워크 토폴로지 분석
   컴퓨터 네트워크의 토폴로지를 트리로 모델링할 때, 후위 순회를 사용하여 네트워크 지연, 대역폭, 신뢰성 등을 분석할 수 있다. 각 하위 네트워크의 특성을 먼저 계산한 후, 상위 네트워크의 특성을 결정한다.

4. XML/HTML 문서 처리
   XML이나 HTML 문서는 트리 구조로 표현될 수 있으며, 문서를 렌더링하거나 처리할 때 후위 순회가 사용된다. 예를 들어, DOM(Document Object Model) 트리를 처리할 때 자식 요소를 먼저 처리한 후 부모 요소를 처리한다.

후위 순회의 변형

1. 역후위 순회(Reverse Postorder Traversal)
   역후위 순회는 오른쪽 서브트리를 먼저 방문한 후 왼쪽 서브트리를 방문하고 마지막으로 루트를 방문하는 방식이다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   def reverse_postorder_traversal(root): result = [] def dfs(node): if not node: return # 오른쪽 서브트리 순회 dfs(node.right) # 왼쪽 서브트리 순회 dfs(node.left) # 현재 노드 방문 result.append(node.value) dfs(root) return result

   이 방법은 그래프의 깊이 우선 탐색(DFS)에서 후위 순회의 역순으로 위상 정렬(topological sort)을 구현할 때 사용될 수 있다.

2. 모리스 후위 순회(Morris Postorder Traversal)
   모리스 후위 순회는 추가 공간을 사용하지 않고(O(1) 공간 복잡도) 트리를 후위 순회하는 알고리즘이다.
   이 방법은 복잡하지만 공간 효율성이 중요한 경우에 유용하다.

   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

   def morris_postorder_traversal(root): result = [] dummy = TreeNode(0) dummy.left = root current = dummy while current: if not current.left: current = current.right else: predecessor = current.left while predecessor.right and predecessor.right != current: predecessor = predecessor.right if not predecessor.right: predecessor.right = current current = current.left else: # 중요한 부분: 왼쪽 서브트리에서 올라오는 경로를 역순으로 기록 temp = [] p = current.left while p != current: temp.append(p.value) p = predecessor.right # 역순으로 결과에 추가 result.extend(reversed(temp)) predecessor.right = None current = current.right return result

   이 구현은 복잡하지만, 트리를 일시적으로 수정하여 추가 공간 없이 후위 순회를 가능하게 한다.

후위 순회를 사용한 실제 문제 해결 예시

1. 이진 트리의 섬세한 연산: 서브트리 제거
   이진 트리에서 특정 값을 가진 모든 서브트리를 제거하는 문제를 생각해봅보면:
   후위 순회는 이러한 상향식 연산에 이상적이다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

   def remove_subtrees_with_value(root, target_value): """ 주어진 값을 가진 모든 서브트리를 트리에서 제거합니다. """ if not root: return None # 왼쪽 서브트리 처리 root.left = remove_subtrees_with_value(root.left, target_value) # 오른쪽 서브트리 처리 root.right = remove_subtrees_with_value(root.right, target_value) # 현재 노드 값이 대상 값이면 현재 서브트리 제거 if root.value == target_value: return None return root

2. 이진 트리 노드의 총합 계산
   이진 트리에서 각 노드 값의 총합을 계산하는 문제도 후위 순회로 효율적으로 해결할 수 있다.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   def sum_of_nodes(root): """ 이진 트리의 모든 노드 값의 합을 계산합니다. """ if not root: return 0 # 왼쪽 서브트리의 합 계산 left_sum = sum_of_nodes(root.left) # 오른쪽 서브트리의 합 계산 right_sum = sum_of_nodes(root.right) # 현재 노드 값을 포함한 총합 반환 return left_sum + right_sum + root.value

효율적인 후위 순회 구현을 위한 최적화 기법

1. 제네레이터를 사용한 지연 평가(Lazy Evaluation)
   Python에서는 제네레이터를 사용하여 메모리 효율적인 후위 순회를 구현할 수 있다:

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   def postorder_traversal_generator(root): """ 이진 트리의 후위 순회를 위한 제네레이터 함수입니다. 메모리 효율적으로 노드를 하나씩 생성합니다. """ if not root: return # 제네레이터를 재귀적으로 호출하고 yield from으로 연결 yield from postorder_traversal_generator(root.left) yield from postorder_traversal_generator(root.right) yield root.value # 사용 예시 for value in postorder_traversal_generator(root): print(value)

   이 방법은 전체 결과 리스트를 메모리에 저장하지 않고, 필요할 때마다 다음 노드를 생성한다.

2. 꼬리 재귀 최적화(Tail Recursion Optimization)
   후위 순회의 기본 재귀 구현은 꼬리 재귀가 아니지만, 약간 수정하여 꼬리 재귀 형태로 변환할 수 있다:

   1 2 3 4 5 6 7 8 9 10 11 12 13

   def postorder_traversal_tail_recursive(root): result = [] def postorder(node, result, cont): if not node: return cont(result) def process_right(result): return postorder(node.right, result, lambda r: cont(r + [node.value])) return postorder(node.left, result, process_right) return postorder(root, result, lambda x: x)

   이 구현은 복잡하지만, 꼬리 재귀 최적화를 지원하는 언어나 컴파일러에서는 스택 오버플로우 위험 없이 효율적으로 실행될 수 있다.

참고 및 출처