[자료구조] 트리

트리

 

단순 선형 자료구조에서는 계층을 나타내기가 어렵다.

따라서 계층적 자료구조를 만들기 위해서 트리를 생각했다.

값을 가지는 노드와, 노드 사이를 잇는 간선으로 이루어져 있으며,

부모 - 자식 관계를 가진다.

트리를 그림으로 나타내면 위와 같다.

여기서 A - B, C, D의 관계를 부모 - 자식 관계라 하며, 

마찬가지로 B - E, F의 관계도 부모 - 자식 관계이다.

 

가장 위에 있는 노드인 A를 루트(Root)노드라 하고,

자식이 없는 노드들(E, F, C, G)를 리프(Leaf)노드라 한다.

 

위의 트리는 3개의 층으로 되어있는데, 이를 높이가 3인 트리라고 한다.

 

트리는 서브트리로 나눌 수 있다.

C도 높이가 0인 트리로 볼 수 있다.

이렇게 나누면 B와 D는 각각의 서브트리에서 루트노드가 된다.

 

트리의 자식이 연결되어 싸이클이 생기면 그래프가 된다.

 

이진트리(Binary Tree)

부모의 자식이 최대 둘인 트리를 이진 트리라 한다.

자료 순회

앞에서부터 쭉 탐색하는 선형구조와 달리 트리는 계층적 구조이므로 여러가지 방식으로 자료를 순회할 수 있다.

• preorder - ABDECF
• inorder - DBEACF
• postorder - DEBFCA
• levelorder - ABCDEF

간단한 이진트리와 순회코드들은 다음과 같다.

from collections import deque
class Node:
    def __init__(self, item):
        self.left = None
        self.right = None
        self.data = item

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

    def preorder(self, n):
        if n:
            print(n.data, end='')
            self.preorder(n.left)
            self.preorder(n.right)
            
    def postorder(self, n):
        if n:
            self.postorder(n.left)
            self.postorder(n.right)
            print(n.data, end='')

    def inorder(self, n):
        if n:
            self.inorder(n.left)
            print(n.data, end='')
            self.inorder(n.right)

    def levelorder(self,n):
        q = deque([n])
        while q:
            cur = q.popleft()
            if cur is not None:
                print(cur.data, end='')
                q.append(cur.left)
                q.append(cur.right)
                
if __name__ == "__main__":
    BT = BinaryTree()
    BT.root = Node('A')
    BT.root.left = Node('B')
    BT.root.right = Node('C')
    BT.root.left.left = Node('D')
    BT.root.left.right = Node('E')
    BT.root.right.right = Node('F')

    print('preorder')
    BT.preorder(BT.root)
    print('\ninorder')
    BT.inorder(BT.root)
    print('\npostorder')
    BT.postorder(BT.root)
    print('\nlevelorder')
    BT.levelorder(BT.root)

위 처럼 코드를 구성하면 BT.root.left.right.~~~ 계속 늘어지게 된다.

삽입 삭제 연산은 다음 글에서 다뤄보자!