Preorder Traversal

전위 순회(Preorder Traversal)

전위 순회(Preorder Traversal)는 트리 자료구조를 탐색하는 가장 기본적인 방법 중 하나이다.

전위 순회는 트리를 탐색하는 깊이 우선 탐색(Depth-First Search, DFS)의 한 형태이다.

이 방법에서는 다음과 같은 순서로 노드를 방문한다:

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

이 과정은 재귀적으로 수행되며, 루트 노드부터 시작하여 왼쪽 가지를 따라 깊이 내려간 후 오른쪽 가지로 이동한다. 전위 순회의 이름에서 “전위(Pre)“는 부모 노드를 자식 노드보다 먼저(before) 방문한다는 의미를 담고 있다.

전위 순회는 트리를 탐색하는 기본적이면서도 강력한 방법이다.
루트를 먼저 방문한 후 왼쪽과 오른쪽 서브트리를 순서대로 방문하는 이 방법은 트리 복제, 표현식 트리 처리, 디렉토리 구조 탐색 등 다양한 문제를 해결하는 데 활용된다.

재귀적 구현이 간결하고 직관적이지만, 스택 오버플로우 위험이 있는 깊은 트리에서는 반복적 방법이나 모리스 순회와 같은 최적화된 알고리즘을 고려해야 할 수 있다.

전위 순회의 알고리즘

아래의 이진 트리를 예로 들어 전위 순회 과정을 살펴보면:

1
2
3
4
5

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

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

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

1. 루트 노드 1을 방문한다.
2. 왼쪽 서브트리로 이동하여 노드 2를 방문한다.
3. 노드 2의 왼쪽 서브트리로 이동하여 노드 4를 방문한다.
4. 노드 4는 자식이 없으므로, 노드 2의 오른쪽 서브트리로 이동하여 노드 5를 방문한다.
5. 노드 5도 자식이 없으므로, 루트 노드 1의 오른쪽 서브트리로 이동하여 노드 3을 방문한다.
6. 노드 3의 왼쪽 서브트리로 이동하여 노드 6을 방문한다.
7. 노드 6은 자식이 없으므로, 노드 3의 오른쪽 서브트리로 이동하여 노드 7을 방문한다.

1
2
3
4
5

        A
       / \
      B   C
     / \   \
    D   E   F

이진 트리의 전위 순회 순서를 구하는 과정은 다음과 같다.

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

재귀적 구현

전위 순회는 재귀를 사용하여 간결하게 구현할 수 있다:

 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

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

def preorder_traversal(node):
    if node is None:
        return
    
    # 현재 노드 출력
    print(node.value, end=" ")
    
    # 왼쪽 서브트리 탐색
    preorder_traversal(node.left)
    
    # 오른쪽 서브트리 탐색
    preorder_traversal(node.right)

# 트리 생성
root = Node('A')
root.left = Node('B')
root.right = Node('C')
root.left.left = Node('D')
root.left.right = Node('E')
root.right.right = Node('F')

# 전위 순회 실행
preorder_traversal(root)

실행 결과:

1

A B D E C F

반복적(비재귀적) 구현

스택을 사용한 반복적 구현 방법도 가능합니다:

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

def preorder_traversal_iterative(root):
    if root is None:
        return
    
    stack = [root]  # 스택에 루트 노드 삽입
    
    while stack:
        node = stack.pop()
        print(node.value, end=" ")  # 현재 노드 방문
        
        # 스택의 특성상 오른쪽 자식을 먼저 삽입해야 왼쪽 자식이 먼저 처리됨
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)

# 실행
preorder_traversal_iterative(root)

실행 결과:

1

A B D E C F

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

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

   1 2 3 4 5

   1 / \ 2 3 / \ / 4 5 6

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

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

   왼쪽 편향 트리:

   1 2 3 4 5 6 7

   1 / 2 / 3 / 4

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

   오른쪽 편향 트리:

   1 2 3 4 5 6 7

   1 \ 2 \ 3 \ 4

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

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

   1 2 3 4 5

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

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

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

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

전위 순회의 활용 사례

1. 트리 복제(Tree Cloning)
   전위 순회는 트리의 복제본을 만드는 데 유용하다.
   각 노드를 방문하면서 새 노드를 생성하고 연결하는 방식으로 트리를 복제할 수 있다.

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

   def clone_tree(node): if node is None: return None # 현재 노드 복제 new_node = TreeNode(node.value) # 왼쪽 서브트리 복제 new_node.left = clone_tree(node.left) # 오른쪽 서브트리 복제 new_node.right = clone_tree(node.right) return new_node

2. 디렉토리 구조 출력
   파일 시스템의 디렉토리 구조를 출력할 때 전위 순회가 자연스러운 방법이다.
   루트 디렉토리부터 시작하여 각 하위 디렉토리와 파일을 순차적으로 탐색한다.

   1 2 3 4 5 6 7 8 9

   def print_directory_structure(path, indent=""): # 현재 디렉토리 출력 print(indent + os.path.basename(path)) # 하위 항목이 디렉토리인 경우 재귀적으로 탐색 if os.path.isdir(path): for item in os.listdir(path): item_path = os.path.join(path, item) print_directory_structure(item_path, indent + " ")

3. 표현식 트리의 전위 표기법(Prefix Notation) 변환
   표현식 트리에서 연산자는 내부 노드에, 피연산자는 리프 노드에 저장된다.
   전위 순회를 사용하면 중위 표기법(infix notation)으로 작성된 수식을 전위 표기법(prefix notation 또는 Polish notation)으로 변환할 수 있다.

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

   1 2 3 4 5

   + / \ a * / \ b c

   전위 순회를 수행하면 + a * b c라는 전위 표기법을 얻을 수 있다.

4. XML/HTML 문서 파싱
   XML이나 HTML과 같은 구조화된 문서는 트리 형태로 표현될 수 있으며, 문서를 파싱할 때 전위 순회가 사용된다.
   먼저 부모 태그를 처리한 후 자식 요소들을 처리한다.

   1 2 3 4 5 6 7 8 9 10 11

   def parse_xml_element(element): # 현재 요소(태그) 처리 print(f"처리 중인 태그: {element.tag}") # 요소의 속성 처리 for attr_name, attr_value in element.attrib.items(): print(f" 속성: {attr_name} = {attr_value}") # 자식 요소 처리 for child in element: parse_xml_element(child)

5. 트리의 직렬화(Serialization)
   트리를 저장하거나 전송하기 위해 선형 구조로 변환하는 과정에서 전위 순회가 사용된다.
   전위 순회의 특성상 부모 노드가 자식 노드보다 먼저 저장되므로, 역직렬화 과정에서 트리를 쉽게 재구성할 수 있다.

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

   def serialize_tree(root): if root is None: return "null," # 현재 노드의 값을 문자열에 추가 serialized = str(root.value) + "," # 왼쪽 서브트리 직렬화 serialized += serialize_tree(root.left) # 오른쪽 서브트리 직렬화 serialized += serialize_tree(root.right) return serialized

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

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

2. 공간 복잡도

   • 재귀적 구현: 재귀 호출 스택의 크기는 트리의 높이 h에 비례하므로 공간 복잡도는 O(h)이다. 최악의 경우(편향 트리)에는 O(n)이 될 수 있다.
   • 반복적 구현: 명시적 스택을 사용하는 경우에도 공간 복잡도는 O(h)이다. 마찬가지로 최악의 경우에는 O(n)이 될 수 있다.

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

1. 전위 순회 vs 중위 순회(Inorder Traversal)

   • 전위 순회: 루트 → 왼쪽 → 오른쪽
   • 중위 순회: 왼쪽 → 루트 → 오른쪽 중위 순회는 이진 검색 트리(BST)에서 노드를 오름차순으로 방문할 때 유용하다. 중위 표기법의 수식을 생성할 때도 사용된다.

2. 전위 순회 vs 후위 순회(Postorder Traversal)

   • 전위 순회: 루트 → 왼쪽 → 오른쪽
   • 후위 순회: 왼쪽 → 오른쪽 → 루트 후위 순회는 트리를 삭제하거나 후위 표기법(postfix notation)의 수식을 생성할 때 유용하다. 자식 노드를 먼저 처리한 후 부모 노드를 처리하는 상향식 접근 방식이다.

3. 전위 순회 vs 레벨 순회(Level Order Traversal)

   • 전위 순회: 깊이 우선(DFS) 방식으로 루트부터 시작하여 왼쪽 가지를 따라 내려간다.
   • 레벨 순회: 너비 우선(BFS) 방식으로 각 레벨의 노드를 왼쪽에서 오른쪽으로 방문한다. 레벨 순회는 최단 경로 문제나 트리의 너비 계산에 유용하다.

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

아래는 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

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

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

def preorder_traversal_iterative(root):
    if not root:
        return []
    
    result = []
    stack = [root]
    
    while stack:
        node = stack.pop()
        result.append(node.value)
        
        # 스택은 LIFO이므로 오른쪽 자식을 먼저 푸시
        if node.right:
            stack.append(node.right)
        if node.left:
            stack.append(node.left)
    
    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("재귀적 전위 순회:", preorder_traversal_recursive(root))  # [1, 2, 4, 5, 3, 6, 7]

# 반복적 방법으로 전위 순회
print("반복적 전위 순회:", preorder_traversal_iterative(root))  # [1, 2, 4, 5, 3, 6, 7]

전위 순회의 변형

1. 모리스 전위 순회(Morris Preorder 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

   def morris_preorder_traversal(root): result = [] current = root while current: # 왼쪽 자식이 없으면 현재 노드를 방문하고 오른쪽으로 이동 if not current.left: result.append(current.value) current = current.right else: # 왼쪽 서브트리에서 가장 오른쪽 노드(중위 순회에서 현재 노드의 선행자)를 찾음 predecessor = current.left while predecessor.right and predecessor.right != current: predecessor = predecessor.right # 선행자의 오른쪽이 None이면, 현재 노드로 연결하고 현재 노드를 방문한 후 왼쪽으로 이동 if not predecessor.right: result.append(current.value) predecessor.right = current current = current.left # 선행자의 오른쪽이 현재 노드를 가리키면, 그 연결을 끊고 오른쪽으로 이동 else: predecessor.right = None current = current.right return result

2. N진 트리의 전위 순회
   N진 트리(각 노드가 N개 이하의 자식을 가질 수 있는 트리)에서도 전위 순회를 적용할 수 있다.

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

   class NaryTreeNode: def __init__(self, value=0): self.value = value self.children = [] def preorder_nary_tree(root): if not root: return [] result = [root.value] for child in root.children: result.extend(preorder_nary_tree(child)) return result

실전 문제: 전위 순회 응용

이진 트리의 경로 합 확인

주어진 이진 트리와 목표 합이 있을 때, 루트에서 리프까지의 경로 중 합이 목표 값과 일치하는 경로가 있는지 확인하는 문제.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def has_path_sum(root, target_sum):
    if not root:
        return False
    
    # 리프 노드에 도달했을 때 합이 목표 값과 일치하는지 확인
    if not root.left and not root.right:
        return root.value == target_sum
    
    # 왼쪽 또는 오른쪽 서브트리에서 경로를 찾음
    return (has_path_sum(root.left, target_sum - root.value) or 
            has_path_sum(root.right, target_sum - root.value))

이진 트리의 전위 순회 결과로부터 트리 재구성

전위 순회의 결과와 중위 순회의 결과가 주어졌을 때, 원래 이진 트리를 재구성하는 문제.

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

def build_tree(preorder, inorder):
    if not preorder or not inorder:
        return None
    
    # 전위 순회의 첫 번째 요소는 루트
    root_value = preorder[0]
    root = TreeNode(root_value)
    
    # 중위 순회에서 루트의 위치 찾기
    root_index = inorder.index(root_value)
    
    # 왼쪽 서브트리와 오른쪽 서브트리로 분할
    root.left = build_tree(preorder[1:1+root_index], inorder[:root_index])
    root.right = build_tree(preorder[1+root_index:], inorder[root_index+1:])
    
    return root

참고 및 출처