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

1. Python에서 처음부터 트리 구현
2. Python에서 이진 트리 탐색
3. Python 라이브러리를 사용하여 트리 구현

트리는 데이터 구조 중 하나입니다. 데이터 구조는 메모리에서 데이터를 구성하는 방법에 불과합니다. 나무는 노드 (정점이라고도 함)와 가장자리의 조합입니다. 나무에는 노드와 가장자리가 얼마든지있을 수 있습니다. 노드는 데이터를 저장하는 곳이고 가장자리는2노드 사이의 경로입니다. 이진 트리, 삼진 트리, 이진 검색 트리, AVL 트리 등 다양한 유형의 트리를 사용할 수 있습니다.

트리의 노드 유형 :

1. 부모 노드 : 하나 이상의 자식이있는 노드입니다.
2. 자식 노드 : 부모 노드가있는 노드입니다.
3. 리프 노드 : 자식이없는 노드입니다.

이 기사에서는 먼저 라이브러리를 사용하지 않고 트리를 처음부터 구현하는 방법을 살펴본 다음 나중에 Python 라이브러리를 사용하여 트리를 구현하는 방법을 살펴 보겠습니다.

Python에서 처음부터 트리 구현

Python에서 트리를 생성하려면 먼저 단일 노드를 나타내는Node클래스를 생성해야합니다. 이Node클래스는 3 개의 변수를 포함합니다. 첫 번째는 왼쪽 자식을 가리키는left, 해당 노드에 대한 값을 포함하는 두 번째 변수data, 오른쪽 자식을 가리키는right변수입니다.

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

트리를 초기화합시다.

root = Node(10)

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

나무는 아래와 같습니다.

          10
        /    \
       34      89
     /    \ 
    45    50 

Node클래스의 객체를 만들 때마다__init__생성자가 호출되고 해당 생성자 내부의 모든 변수가 초기화됩니다. root는 값이10인 트리의 루트 노드를 포함하고root.left및root.right를 사용하여 값이34및 오른쪽 인 왼쪽 자식을 삽입합니다. 값이89인 루트 노드의 하위. 바이너리 트리이므로 모든 노드에는 최대 2 개의 노드가 포함됩니다.

마지막으로 노드34의 자식으로 두 개의 노드, 즉45및50을 트리에 추가합니다. 만들고있는 트리 유형에 따라 트리 안에 원하는 수의 노드를 삽입 할 수 있습니다.

Python에서 이진 트리 탐색

이제 트리를 만들었으므로 트리를 가로 질러 트리 요소를 인쇄 해 보겠습니다. 순회는 트리의 모든 노드를 방문합니다. 트리의 모든 노드는 순회에서 세 번 방문됩니다. 나무를 횡단하는 방법은 위에서 아래로, 왼쪽에서 오른쪽으로입니다.

선주문 순회

트리를 순회하는 동안 노드를 처음 볼 때마다 해당 노드를 인쇄 한 다음 왼쪽 노드에서 재귀를 수행 한 다음 오른쪽 노드에서 재귀를 수행합니다.

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

출력:

10 
34 
45 
50 
89

순서 내 순회

순회 순회를 수행하는 동안 먼저 왼쪽 노드에서 재귀를 수행 한 다음 동일한 노드를 두 번째로 방문하면 해당 노드를 인쇄합니다. 그런 다음 오른쪽 노드에서 재귀를 수행합니다.

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

출력:

45 
34 
50 
10 
89

주문 후 순회

Post-order traversal의 경우 왼쪽 노드와 오른쪽 노드에서 재귀를 수행 한 다음 동일한 노드를 세 번째로 방문하면 해당 노드를 인쇄합니다.

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

출력:

45
50
34
89
10

Python 라이브러리를 사용하여 트리 구현

우리가 보았 듯이 트리를 처음부터 구현하려면 시간이 걸리고 많은 코드가 필요합니다. Python에서 트리를 구현하는 더 쉬운 방법은anytree라는 라이브러리를 사용하는 것입니다. anytree라이브러리를 사용하면 많은 코드를 작성하지 않고도 트리를 만들 수 있습니다.

anytree라이브러리를 사용하려면 먼저 아래 명령의 도움말을 사용하여 설치해야합니다.

pip install anytree

여기에서도 이전에 만든 것과 동일한 트리를 만들고 있습니다. 이제anytree라이브러리에서Node및RenderTree를 가져올 수 있습니다.

from anytree import Node, RenderTree

root = Node(10)

level_1_child_1 = Node(34, parent=root)
level_1_child_2 = Node(89, parent=root)
level_2_child_1 = Node(45, parent=level_1_child_1)
level_2_child_2 = Node(50, parent=level_1_child_2)

for pre, fill, node in RenderTree(root):
    print("%s%s" % (pre, node.name))

# Tree Structure
#          10
#        /    \
#       34      89
#     /    \
#    45    50

출력:

10
├── 34
│   └── 45
└── 89
    └── 50

여기서Node는 두 개의 매개 변수를 취하는 노드를 생성합니다. 첫 번째는 노드의 값이고 두 번째는 상위 노드의 이름입니다 (선택적 매개 변수). 트리에서root노드는 부모가없는 유일한 노드이기 때문에root노드를 생성하는 동안 첫 번째 매개 변수 인 노드의 값만 전달하고 두 번째 매개 변수는 전달하지 않습니다. RenderTree메소드는 출력에 표시된대로 전체 트리를 인쇄하는 데 도움이됩니다.