[알고리즘](Python) 트리

참고 자료: 파이썬으로 배우는 자료 구조 핵심 원리(양태환)

 

7.1 트리 용어 정리

관계

트리에는 관계의 개념으로,

부모(parent), 자식(child), 조상(ancestor), 자손(descendant)가 있다.

노드 2와 노드 3은 노드 1의 자식이다. 반대로 노드1은 노드 2,3의 부모이자 루트 노드이다.

노드 1은 노드 4,5,6,7,8의 조상이다. 반대로 노드 4,5,6,7,8은 노드 1의 자손이다.

차수

차수(degree)란 어떤 노드의 자식 노드 개수를 의미한다.

트리의 차수는 트리에 있는 노드의 최대 차수 즉, 최대 자식 노드 개수를 의미한다.

 

리프 노드(leaf node)는 차수가 0인 노드를 의미한다. 즉, 자식이 없는 노드이다.

내부 노드(internal node)는 루트 노드와 리프 노드를 제외한 노드를 의미한다.

레벨

레벨(level)은 루트의 레벨을 1로 하고 자식으로 내려가며 더해지는 개념으로 깊이와 연관이 있다.

트리의 깊이/높이는 트리가 갖는 최대 레벨을 의미한다.

이진 트리

이진 트리(binary tree)는 트리를 구성하는 노드의 자식이 최대 두 개인 트리다.

포화 이진 트리(full binary tree)란 모든 레벨에 가능한 모든 노드가 있는 트리다.

완전 이진 트리(complete binary tree)란 마지막에서 두 번째의 노드는 꽉 차있고, 마지막 레벨에서는 노드가 왼쪽에서 오른쪽으로 채워져 있는 트리다.

편향 이진 트리(skewed binary tree)는 왼쪽이나 오른쪽 서브 트리만 가진 트리다.

서브 트리는 어떤 노드의 자식이 이루는 트리를 서브 트리(subtree)라고 한다.

7.2 이진 트리의 순회

이진 트리의 순회는 방문하는 노드의 순서에 따라 그 명칭이 정해진다. 각각의 방문 순서는 아래와 같다.

• 전위 순회: 현재 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리
• 중위 순회: 왼쪽 서브 트리 -> 현재 노드 -> 오른쪽 서브 트리
• 후위 순회: 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 현재 노드

전위 순회(preoreder travaersal)

전위 순회의 방문 순서는 현재 노드 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리 순이다.

순서를 그림으로 확인하면 아래와 같다.

현재 노드를 거쳐 왼쪽 서브 트리로 갔다가, 모든 노드를 다 순회하면 다시 오른쪽 서브 트리를 순회한다.

왼쪽 자식을 방문할 때 왼쪽 자식이 루트로 있는 서브 트리의 노드를 모두 방문하는 것이다. 이때 왼쪽 자식을 루트로 하는 트리를 다시 전위 순회하게 된다.

따라서 트리를 재귀적으로 방문하며 전위 순회를 수행하는 것이다.

재귀적인 구조를 갖기 때문에 트리 순회는 재귀 함수로 구현할 수 있다.

순회 구현

class TreeNode:
    def __init__(self, data=None):
        self.__data = data
        self.__left = None
        self.__right = None

    def __del__(self):
        print('data {} is deleted'.format(self.__data))

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

# 중위 순회
def inorder(cur):
    if not cur:
        return

    inorder(cur.left)

    print(cur.data, end='  ')

    inorder(cur.right)

# 후위 순회
def postorder(cur):
    if not cur:
        return

    postorder(cur.left)
    postorder(cur.right)
    print(cur.data, end='  ')