자료구조 핵심 원리 - 트리

1.1 트리 용어 정리

트리는 그래프 일종이므로 그래프에서 사용하는 용어를 대부분 적용할 수 있습니다. 다만 그래프에서 정점이라고 하는 것을 트리에서는 노드라고 합니다.

 

 

root는 노드 1입니다. 노드 2와 노드 3은 노드 1의 자식(child)입니다. 노드 1은 노드 2와 노드 3의 부모(parent)입니다. 노드 1은 노드 4, 노드 5, 노드 6, 노드 7, 노드 8의 조상(ancestor)입니다. 노드 4, 노드 5, 노드 6, 노드 7, 노드 8은 노드 1의 자손(descendant)입니다.

 

그래프 용어에서 차수(degree)를 배운 적이 있습니다. 트리에도 차수 개념이 있는데, 트리에서는 좀 더 특정 지어서 차수란 ‘어떤 노드의 자식 노드 개수’를 의미합니다. 트리의 차수(degree of a tree)는 트리에 있는 노드의 최대 차수를 의미합니다. 리프 노드(leaf node)는 차수가 0인 노드를 의미합니다. 즉, 자식이 없다는 의미입니다.

 

레벨(level)은 루트의 레벨을 레벨 1로 하고 자식으로 내려가면서 하나씩 더해지는 개념입니다. 즉, 깊이와 연관이 있습니다. 어떤 트리의 깊이(depth) 혹은 높이(height)는 트리가 가지는 최대 레벨을 의미합니다.

 

루트를 가진 트리 말고 일반적인 정의의 트리(즉, 사이클이 없는 연결된 그래프)에서 노드와 에지 사이에는 아주 중요한 수식이 있습니다. 노드 개수를 n이라고 하고 에지 개수를 e라고 했을 때, e = n - 1이 성립됩니다. 이 식이 중요한 이유는 이 트리에 에지가 하나라도 추가되면, 즉 e > n-1이 되는 순간 이 트리에는 사이클이 생겨서 더 이상 트리가 아니게 되기 때문입니다. 이 수식은 크루스칼 알고리즘에서 아주 중요한 역할을 합니다.

 

이진 트리(binary tree)란 트리를 구성하는 노드의 자식이 최대 두 개인 트리를 의미합니다. 그럼 모든 노드를 아예 자식이 없는 경우, 자식을 하나 가진 경우, 자식을 둘 가진 경우로 나눌 수 있겠지요. 자식이 둘이므로 왼쪽 자식과 오른쪽 자식으로 구분합니다.

 

 

레벨 4의 최대 노드 개수는 2의 3제곱이기 때문에 8개입니다.

 

포화 이진 트리(full binary tree)란 높이가 h일 때 노드 개수가 2h-1인 트리입니다. 모든 레벨에 가능한 모든 노드가 있습니다. 완전 이진 트리(complete binary tree)란 높이가 h일 때 레벨 h-1까지 노드 개수는 2h-1-1이고 레벨 h에서는 노드가 왼쪽에서 오른쪽으로 채워지는 트리입니다.

 

 

1.2 이진 트리의 순회 : 모든 노드 방문하기

트리는 그래프의 일종으로 사이클이 없는 비선형 자료 구조입니다. DFS와 BFS를 이용할 수 있습니다. DFS는 스택을 이용하고, BFS는 큐를 이용합니다. 트리에서는 DFS 일종으로 전위, 중위, 후위 순회가 있습니다. 방문 순서를 나누는 겁니다. BFS 일종으로는 레벨 순서 순회가 있습니다. 

 

 

전외 순회는 루트 노드인 1을 방문하고 왼쪽 자식을 방문합니다. 왼쪽 자식도 자신을 루트로 한 이진 트리입니다. 즉, 왼쪽 자식을 방문했다는 것은 왼쪽 자식이 루트로 있는 서브 트리의 노드를 모두 방문하는 것입니다. 방문을 재귀적으로 수행하는 방식입니다. 왼쪽 서브 트리를 모두 방문한 후 마지막으로 오른쪽 자식을 방문합니다. 위 그림의 이진 트리 방문 순서는 1-2-4-5-3-6-7이 됩니다.

 

전위 순회는 DFS 일종입니다. 즉, 스택 계열의 함수이므로 재귀 함수로 구현하거나 스택 자료구조와 반복문을 이용해서 구현할 수 있습니다. 

 

먼저 트리 노드를 구현합니다. 넣을 데이터와 왼쪽, 오른쪽 자식을 구현해줍니다.

 

# bianry_tree.py

class TreeNode:
    def __init__(self, data=None):
        self.__data = data
        self.__left = None
        self.__right = None
        
        
    def __del__(self):
        print(f"data {self.__data} is deleted.")
        
    @property
    def data(self):
        return self.__data
    
    @data.setter
    def data(self, data):
        self.__data = data
        
    @property
    def left(self):
        return self.__left
    
    @left.setter
    def left(self, left):
        self.__left = left
        
    @property
    def right(self):
        return self.__right
    
    @right.setter
    def right(self, right):
        self.__right = right

 

 

이후 전위 순회를 구현합니다.

 

def preorder(cur):
    if not cur:
        return
    
    print(cur.data, end=' ')
    preorder(cur.left)
    preorder(cur.right)