트리순회 | Notion

트리 순회(Tree Traversal)는 트리 구조에서 모든 노드를 효율적으로 방문하는 방법을 말합니다. 트리는 계층 구조로 노드들이 연결되어 있기 때문에 특정 순서로 노드를 방문하는 방법이 중요합니다. 주요한 트리 순회 방법으로는 세 가지가 있습니다: 전위 순회(pre-order traversal), 중위 순회(in-order traversal), 후위 순회(post-order traversal).

다음은 각각의 순회 방법에 대한 설명입니다:

전위 순회 (Pre-order Traversal): 전위 순회는 루트 노드를 먼저 방문한 후 왼쪽 서브트리를 전위 순회하고 오른쪽 서브트리를 전위 순회하는 방법입니다. 즉, 루트 노드 → 왼쪽 서브트리 → 오른쪽 서브트리 순서로 방문합니다. 전위 순회는 노드의 값을 읽어오는 작업에 주로 사용됩니다.
중위 순회 (In-order Traversal): 중위 순회는 왼쪽 서브트리를 중위 순회한 후 루트 노드를 방문하고, 오른쪽 서브트리를 중위 순회하는 방법입니다. 즉, 왼쪽 서브트리 → 루트 노드 → 오른쪽 서브트리 순서로 방문합니다. 중위 순회는 트리의 노드들을 오름차순으로 정렬된 순서로 읽어오는 작업에 주로 사용됩니다.
후위 순회 (Post-order Traversal): 후위 순회는 왼쪽 서브트리를 후위 순회한 후 오른쪽 서브트리를 후위 순회하고, 마지막으로 루트 노드를 방문하는 방법입니다. 즉, 왼쪽 서브트리 → 오른쪽 서브트리 → 루트 노드 순서로 방문합니다. 후위 순회는 트리의 노드들을 처리하는 작업을 할 때 사용됩니다.

트리 순회는 트리 내의 노드를 모두 방문하거나, 특정 조건에 맞는 노드를 찾을 때 유용합니다. 이러한 순회 방법은 컴퓨터 과학과 프로그래밍에서 널리 사용되며, 이진 트리, 이진 검색 트리, 힙 등 다양한 트리 구조에서 적용될 수 있습니다.

전위 순회 (Pre-order Traversal):

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

def pre_order_traversal(root):
    if root is not None:
        print(root.value, end=" ")  # 현재 노드 방문
        pre_order_traversal(root.left)  # 왼쪽 서브트리 순회
        pre_order_traversal(root.right)  # 오른쪽 서브트리 순회

# 예시 이진 트리 생성
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("전위 순회 결과:", end=" ")
pre_order_traversal(root)

중위 순회 (In-order Traversal):

def in_order_traversal(root):
    if root is not None:
        in_order_traversal(root.left)  # 왼쪽 서브트리 순회
        print(root.value, end=" ")  # 현재 노드 방문
        in_order_traversal(root.right)  # 오른쪽 서브트리 순회

print("중위 순회 결과:", end=" ")
in_order_traversal(root)

후위 순회 (Post-order Traversal):

def post_order_traversal(root):
    if root is not None:
        post_order_traversal(root.left)  # 왼쪽 서브트리 순회
        post_order_traversal(root.right)  # 오른쪽 서브트리 순회
        print(root.value, end=" ")  # 현재 노드 방문

print("후위 순회 결과:", end=" ")
post_order_traversal(root)

이 코드들은 각각 전위, 중위, 후위 순회를 구현한 예시입니다. 트리의 노드를 클래스로 정의하고, 해당 클래스의 인스턴스들을 구성하여 트리를 생성하고 탐색합니다.