파이썬 코딩테스트 강좌, 트리 순회하기

소개

알고리즘 문제 해결은 소프트웨어 개발자에게 매우 중요한 과정입니다. 특히, 트리는 많은 문제의 핵심 구조로 사용되며,
트리를 순회하는 방법을 이해하는 것은 이 구조를 효과적으로 활용하는 데 필수적입니다.
이 글에서는 트리의 기본 개념과 파이썬을 이용한 다양한 순회 방법에 대해 설명하고, 실제 알고리즘 문제를 해결해보는
과정을 통해 이론을 실습으로 연결해보겠습니다.

트리의 기초

트리는 노드와 노드 간의 연결로 이루어진 비선형 자료구조입니다.
각각의 노드는 자식 노드를 가질 수 있으며, 이 구조는 계층성을 표현하기에 적합합니다.
가장 위에 있는 노드를 루트 노드라고 하며, 노드 간의 관계를 유도하는 다양한 탐색 방법이 존재합니다.

트리의 종류

– 이진 트리: 각 노드가 최대 두 개의 자식 노드를 가지는 트리
– 이진 탐색 트리: 정렬된 이진 트리로, 왼쪽 자식은 부모 노드보다 작고, 오른쪽 자식은 크다
– AVL 트리: 균형 이진 탐색 트리로, 높이 차이가 1 이하로 유지된다

트리 순회 방식

트리 순회는 노드를 방문하는 순서를 정의합니다. 주요 순회 방식은 다음과 같습니다.

1. 전위 순회 (Pre-Order Traversal)

전위 순회는 노드 자체를 먼저 방문한 후, 왼쪽 자식 노드를 재귀적으로 방문하고, 이후 오른쪽 자식 노드를 방문하는 방법입니다.
즉, 방문 순서는 다음과 같습니다: 노드 → 왼쪽 → 오른쪽

2. 중위 순회 (In-Order Traversal)

중위 순회는 먼저 왼쪽 자식 노드를 방문한 후, 노드를 방문하고 마지막으로 오른쪽 자식 노드를 방문하는 방식입니다.
순서는 다음과 같습니다: 왼쪽 → 노드 → 오른쪽

3. 후위 순회 (Post-Order Traversal)

후위 순회는 왼쪽 자식 노드를 방문하고 오른쪽 자식 노드를 방문한 후, 마지막으로 노드를 방문하는 방법입니다.
순서는 다음과 같습니다: 왼쪽 → 오른쪽 → 노드

문제: 이진 트리 순회 결과값 출력하기

다음은 이진 트리의 노드를 입력받아 전위, 중위 및 후위 순회의 결과를 출력하는 문제입니다.
입력으로는 각 노드의 값을 담고 있는 리스트가 주어질 때, 트리의 순회 결과를 리턴해야 합니다.

문제 설명

주어진 리스트를 기반으로 이진 트리를 구성한 후, 각 순회 방법을 이용하여 결과를 담은 리스트를 반환합니다.
가령, 리스트가 [1, 2, 3, 4, 5]라면, 다음과 같은 트리를 구성할 수 있습니다:

입력 / 출력 형식

입력: 각 노드를 담고 있는 리스트가 주어짐.
출력: 전위, 중위 및 후위 순회 결과 리스트

문제 해결 과정

1단계: 트리 구조 정의하기

트리를 구성하기 위해 먼저 노드를 나타내는 클래스를 정의하겠습니다.

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

2단계: 트리 구축하기

주어진 리스트를 기반으로 트리를 구축하는 함수를 작성합니다.
이 예제에서는 간단히 리스트의 첫 번째 값을 루트 노드로 설정하고 나머지를 왼쪽 자식과 오른쪽 자식으로 배치합니다.

def build_tree(values):
    if not values:
        return None
    root = TreeNode(values[0])
    for value in values[1:]:
        insert_node(root, value)
    return root

def insert_node(root, value):
    if value < root.value:
        if root.left is None:
            root.left = TreeNode(value)
        else:
            insert_node(root.left, value)
    else:
        if root.right is None:
            root.right = TreeNode(value)
        else:
            insert_node(root.right, value)

3단계: 순회 함수 작성하기

각각의 순회 방식을 구현합니다. 재귀적으로 트리를 탐색하며 노드를 리스트에 저장합니다.

def preorder_traversal(root):
    result = []
    if root:
        result.append(root.value)
        result.extend(preorder_traversal(root.left))
        result.extend(preorder_traversal(root.right))
    return result

def inorder_traversal(root):
    result = []
    if root:
        result.extend(inorder_traversal(root.left))
        result.append(root.value)
        result.extend(inorder_traversal(root.right))
    return result

def postorder_traversal(root):
    result = []
    if root:
        result.extend(postorder_traversal(root.left))
        result.extend(postorder_traversal(root.right))
        result.append(root.value)
    return result

4단계: 통합하여 호출하기

최종적으로 위의 모든 함수를 통합하여 문제를 해결합니다.

def traverse_tree(values):
    root = build_tree(values)
    return {
        'preorder': preorder_traversal(root),
        'inorder': inorder_traversal(root),
        'postorder': postorder_traversal(root),
    }

# 예제 사용
input_values = [1, 2, 3, 4, 5]
result = traverse_tree(input_values)
print(result)  # 결과 출력

최종 결과 및 정리

위의 과정을 통해 우리는 입력받은 이진 트리 리스트를 순회하여 전위, 중위, 후위 순회의 결과를 도출할 수 있습니다.
이 문제를 통해 트리 순회의 개념과 이를 효율적으로 구현하는 방법에 대해 배웠습니다.
추가적으로 다양한 트리 구조와 순회 방식에 대해서도 경험하고 실습해보기를 권장합니다.

소개