[파이썬] 트리 순회 알고리즘 (전위, 중위, 후위)의 구현

04 Sep 2023

python

트리는 계층적인 구조를 갖는 자료 구조로, 데이터를 효율적으로 저장하고 검색할 수 있습니다. 트리의 각 노드는 자식 노드를 가지고 있으며, 이를 이용하여 데이터를 효율적으로 조작할 수 있습니다. 트리의 노드를 순회하면서 데이터에 접근하는 것은 매우 중요한 작업인데요, 이때 사용되는 알고리즘에는 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)가 있습니다.

전위 순회 (Preorder Traversal)

전위 순회는 루트 노드를 먼저 방문한 후, 왼쪽 서브트리를 순회한 뒤 오른쪽 서브트리를 순회하는 방법입니다. 전위 순회는 다음과 같은 순서로 노드를 순회합니다:

현재 노드를 출력 (또는 다른 작업 수행)
왼쪽 서브트리로 이동
오른쪽 서브트리로 이동

아래는 전위 순회 알고리즘의 구현 예시입니다:

def preorder_traversal(node):
    if node is not None:
        # 현재 노드 처리 (출력 또는 다른 작업 수행)
        print(node.value)

        # 왼쪽 서브트리 순회
        preorder_traversal(node.left)

        # 오른쪽 서브트리 순회
        preorder_traversal(node.right)

중위 순회 (Inorder Traversal)

중위 순회는 왼쪽 서브트리를 먼저 순회한 뒤, 루트 노드를 방문하고 오른쪽 서브트리를 순회하는 방법입니다. 중위 순회는 다음과 같은 순서로 노드를 순회합니다:

왼쪽 서브트리로 이동
현재 노드 출력 (또는 다른 작업 수행)
오른쪽 서브트리로 이동

아래는 중위 순회 알고리즘의 구현 예시입니다:

def inorder_traversal(node):
    if node is not None:
        # 왼쪽 서브트리 순회
        inorder_traversal(node.left)

        # 현재 노드 처리 (출력 또는 다른 작업 수행)
        print(node.value)

        # 오른쪽 서브트리 순회
        inorder_traversal(node.right)

후위 순회 (Postorder Traversal)

후위 순회는 왼쪽 서브트리를 먼저 순회한 뒤, 오른쪽 서브트리를 순회하고 마지막으로 루트 노드를 방문하는 방법입니다. 후위 순회는 다음과 같은 순서로 노드를 순회합니다:

왼쪽 서브트리로 이동
오른쪽 서브트리로 이동
현재 노드 출력 (또는 다른 작업 수행)

아래는 후위 순회 알고리즘의 구현 예시입니다:

def postorder_traversal(node):
    if node is not None:
        # 왼쪽 서브트리 순회
        postorder_traversal(node.left)

        # 오른쪽 서브트리 순회
        postorder_traversal(node.right)

        # 현재 노드 처리 (출력 또는 다른 작업 수행)
        print(node.value)

적용 예시

이제 위에서 구현한 전위, 중위, 후위 순회 알고리즘을 사용하여 트리를 순회해보겠습니다. 아래는 트리의 노드를 나타내는 TreeNode 클래스의 예시입니다:

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

아래는 예시 트리를 생성하고 순회하는 코드입니다:

# 예시 트리 생성
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)

# 전위 순회
preorder_traversal(root)

# 중위 순회
inorder_traversal(root)

# 후위 순회
postorder_traversal(root)

위 코드를 실행하면 트리의 노드값을 전위, 중위, 후위 순서로 출력할 수 있습니다.

트리 순회 알고리즘은 데이터의 구조를 파악하거나 특정 작업을 수행하기 위해 매우 중요한 알고리즘입니다. 이해하고 활용하는 것은 데이터 구조와 관련된 문제를 해결하는데 큰 도움이 될 것입니다.