자료구조-트리 Python(파이썬)

참고 사이트: https://www.delftstack.com/ko/howto/python/trees-in-python/

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

트리란 그래프의 일종으로 여러 노드가 한 노드를 가리킬 수 없는 구조이다. 간단하게는 회로가 없고 서로 다른 두 노드를 잇는 길이 하나뿐인 그래프를 트리라고 부른다.

 

트리 노드 유형:

1. 부모 노드: 하나 이상의 자식이 있는 노드

2. 자식 노드: 부모 노드가 있는 노드

3. 리프 노드: 자식이 없는 노드

파이썬 트리 구현

내장함수를 이용하지 않고 구현하는 방법이다. 파이썬에서 트리를 생성시 먼저 단일 노드를 나타내는 node 클래스를 생성한다. 노드 클래스는 3개의 변수를 포함하며, 1번째는 왼쪽 자식, 2번째는 해당 노드의 값, 3번째는 오른쪽 자식을 가리키는 변수들을 만들어낸다

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 

이진 트리의 탐색

트리를 탐색하는 방법에는 전위순회, 중위순회, 후위순회 3가지로 본다.

순회를 하는데 있어서 기초적인 개념으로 재귀를 사용한다.

 

먼저 전위 순회이다. 노드 첫 발견시 인쇄 후 왼쪽 노드에서 재귀를 수행하고 그 후 오른쪽 노드에서 재귀를 수행한다.

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

출력: 10 34 45 50 89

 

중위 순회의 경우 왼쪽 노드에서 재귀를 수행하고 2번째로 방문한 노드를 인쇄, 그 후 오른쪽 노드에서 재귀를 수행한다.

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

출력: 45 34 50 10 89

 

후위 순회의 경우 왼쪽노드와 오른쪽 노드에 재귀를 수행한 후 3번쨰 방문한 노드를 인쇄한다.

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

출력: 45 50 34 89 10

 

파이썬 라이브러리 anytree 사용시 노드, 트리를 더 쉽게 구현할 수 있다.

pip install anytree

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))

출력: 

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