Python에서 트리 데이터 구조 구현

트리는 간선으로 연결된 노드로 데이터를 구성합니다. 각 간선은 부모 노드와 자식 노드를 연결하며, 자식이 없는 노드는 리프입니다. 트리에는 이진 트리, 삼진 트리, 이진 검색 트리, AVL 트리 등이 있습니다. 이진 트리에서는 각 노드에 자식이 최대 두 개까지 있을 수 있습니다. 이 가이드에서는 사용자 정의 Node 클래스로 작은 이진 트리를 만들고, 세 가지 깊이 우선 순회 방식으로 탐색한 다음, 라이브러리 대안인 anytree를 소개합니다.

Python에서 트리 구조를 처음부터 구현하기

간단한 이진 트리 노드에는 값을 저장할 공간과 두 자식 노드를 가리킬 참조가 필요합니다. 아래 Node 클래스는 값을 data에 저장합니다. left와 right는 처음에 None이며, 나중에 자식 노드를 가리키도록 지정할 수 있습니다. 이 객체들을 서로 연결하면 트리가 만들어집니다.

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


root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

여기서 root는 34와 89의 부모입니다. 노드 45와 50은 34의 자식이며, 89, 45, 50은 리프입니다. 각 노드가 자식 참조를 최대 두 개까지만 가지므로 이 구조는 이진 트리입니다. 다른 종류의 트리는 고정된 left와 right 속성 대신 자식 노드 모음을 사용하는 등 다른 표현 방식이 필요할 수 있습니다.

Python에서 이진 트리 순회하기

순회는 모든 노드를 한 번씩 처리하며, 재귀 호출을 기준으로 현재 노드를 어느 시점에 방문하느냐에 따라 순서가 정해집니다. 전위 순회는 현재 노드를 먼저 방문한 다음 왼쪽과 오른쪽 하위 트리를 방문합니다. 중위 순회는 왼쪽 하위 트리, 현재 노드, 오른쪽 하위 트리 순으로 방문합니다. 후위 순회는 두 하위 트리를 모두 방문한 뒤 현재 노드를 방문합니다. 아래의 전체 예제는 앞 절과 같은 트리를 만들고 각 순회 결과를 출력합니다.

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


def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)


def inorder(node):
    if node:
        inorder(node.left)
        print(node.data)
        inorder(node.right)


def postorder(node):
    if node:
        postorder(node.left)
        postorder(node.right)
        print(node.data)


root = Node(10)
root.left = Node(34)
root.right = Node(89)
root.left.left = Node(45)
root.left.right = Node(50)

print("Pre-order:")
preorder(root)
print("In-order:")
inorder(root)
print("Post-order:")
postorder(root)

재귀 호출은 첫 번째 절에서 만든 것과 같은 left 및 right 참조를 따라갑니다. 다른 트리에도 적용하려면 순회 함수는 그대로 두고 노드 생성 부분을 바꾸면 됩니다. 방문 시점에 따라 값의 순서가 결정됩니다.

Python 라이브러리로 트리 구현하기

이 작은 이진 트리 예제보다 노드가 많거나 더 다양한 기능이 필요한 경우, anytree를 사용하면 노드 간 관계를 표현하고 트리를 렌더링할 수 있습니다. 프로젝트 환경에 pip install anytree로 설치하세요. 이 API에서 Node는 노드 이름을 위치 인수로 받습니다. 자식을 연결하려면 parent=root를 키워드 인수로 전달합니다. RenderTree는 계층 구조를 순회하며 각 수준을 표시하는 데 사용할 접두 문자열을 제공합니다.

위와 같은 구조를 만들려면 root = Node("10")을 실행한 다음 Node("34", parent=root)와 Node("89", parent=root)를 만듭니다. Node("45", parent=left_child)와 Node("50", parent=left_child)를 만들어 두 리프를 34 아래에 배치한 다음, for pre, fill, node in RenderTree(root)로 순회하면서 pre + node.name을 출력합니다. 이 코드는 라이브러리 API 사용법을 설명하며, 실행 증거는 포함되어 있지 않습니다.