파이썬 자료구조 - Tree

이진 트리(binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리형 자료구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 

이진 트리

아래 코드에선 Node 클래스에서 left를 왼쪽 자식으로, right를 오른쪽 자식으로 표현했다. BinaryTree 클래스는 트리의 맨 위쪽(root)을 정해준다. 각 알파벳에 해당하는 노드를 만든 후, add___로 연결한 다음, 마지막에 root를 정해주는 방식으로 진행할 것이다.

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

    def addLeft(self, Node):
        self.left = Node
        
    def addRight(self, Node):
        self.right = Node   

class BinaryTree:
    def __init__(self,root):
        self.root = root

첫번째 사진과 같은 트리를 만들어보자. Node를 각각 만든다.

a = Node('A')
b = Node('B')
c = Node('C')
d = Node('D')
e = Node('E')
f = Node('F')
g = Node('G')
h = Node('H')
i = Node('I')

이 노드들을 사진과 같도록 연결해야한다. 이때 사용해야할 함수는 addLeft, addRight 이므로 사진과 맞게 연결해주면 된다. 마지막에 BinaryTree를 이용해 a를 root로 만들어주면 끝난다.

a.addLeft(b)
a.addRight(c)
b.addLeft(d)
b.addRight(e)
e.addRight(h)
c.addLeft(f)
c.addRight(g)
g.addLeft(i)

t = BinaryTree(a)

트리구조를 사용하는 이유는 탐색이 빠르기 때문이다. 우리가 컴퓨터의 한 파일을 찾으려고 할 때 모든 폴더를 열어보지 않고 관련 폴더들만 여는 것과 같다.

 

다음번엔 전위 순회, 중위 순회, 후위 순회를 공부할 예정이다.