[자료구조] 트리 2. 이진 트리의 활용

앞서 이진 트리의 개념과 표현법에 대해 간략하게 공부했다.
그럼 이렇게 이진 트리를 만들고 난 후, 어떻게 트리의 데이터에 접근할 수 있을까?

바로 순회를 이용하는 것이다.

순회란 트리에 속하는 모든 노드들을 한 번씩 방문하여 트리의 데이터에 접근하는 것으로, 트리에서 가장 기본적인 연산이다.

이진 트리의 표준 순회에는 전위 순회, 중위 순회, 후위 순회 3가지 방법이 있다.
이들은 루트의 왼쪽 서브 트리, 오른쪽 서브 트리를 각각 어떤 순서로 방문하느냐에 따라 구분된다.
루트를 방문하는 작업을 V, 왼쪽과 오른쪽 서브 트리를 방문하는 작업을 각각 L과 R이라고 할 때,

각 순회들을 구현하는 방법들은 아래와 같다.

• 전위 순회: VLR
• 중위 순회: LVR
• 후위 순회: LRV

---

순회의 구현

def preorder(n): # 전위 순회
    if n is not None:
        print(n.data, end=" ")
        preorder(n.left)
        preorder(n.right)

def inorder(n): # 중위 순회
    if n is not None:
        inorder(n.left)
        print(n.data, end=" ")
        inorder(n.right)

def postorder(n): # 후위 순회
    if n is not None:
        postorder(n.left)
        postorder(n.right)
        print(n.data, end=" ")

코드를 보면… 재귀로 처리해서 굉장히 간단한 모습을 볼 수 있다.
당연한 게 모든 노드에서는 자신이 루트가 되는 서브트리가 또다시 이루어지기 때문에… 출력을 재귀로 처리하면 모든 노드를 순회할 수 있다.


이 세 순회는 단지 어떤 자식에게 먼저 들어가느냐의 차이만 존재할 뿐이다.
그러나 이렇게 자식만을 먼저 순회하는 방법만 존재하는가? 그것은 아니다.
우리는 앞서 트리의 레벨에 대해 배웠다. 이 트리의 레벨 순서대로 순회하는 레벨 순회도 존재한다.

def levelorder(root): # 레벨 순회
    q = Queue.CircularQueue()

    q.enqueue(root)
    while not q.isEmpty():
        n = q.dequeue()
        if n is not None:
            print(n.data, end=" ")
            q.enqueue(n.left)
            q.enqueue(n.right)

코드를 보면 알 수 있듯이 레벨 순회에는 큐가 사용된다.
큐에서 보드를 하나 꺼내 방문하고, 그 자식들을 큐에 삽입한다(왼쪽 자식 우선). 이 과정을 큐가 공백 상태가 될 때까지 반복하는 것이다.

우리는 지금까지 이진 트리에 대해 살펴보았다.
이진 트리는 트리에서 가장 보편적인 형태로, 가장 널리 이용되는 자료구조 중 하나이다.
그런데 우리는 트리의 노드와 순회밖에 구현하지 않았다. 그런데 트리의 연산이 순회 뿐일까?
절대 아니다. 사용자의 기호에 따라 다양한 연산을 구현할 수 있다.

def count_node(n): # 트리의 모든 노드 개수 구하기
    if n is None:
        return 0
    else:
        return 1 + count_node(n.left) + count_node(n.right)

def count_leaf(n): # 트리의 리프 노드 개수 구하기
    if n is None:
        return 0
    elif n.left is None and n.right is None:
        return 1
    else:
        return count_leaf(n.left) + count_leaf(n.right)

def calc_height(n): # 트리의 높이 구하기
    if n is None:
        return 0
    hLeft = calc_height(n.left)
    hRight = calc_height(n.right)
    if (hLeft > hRight):
        return hLeft + 1
    else:
        return hRight + 1

---

이진 트리의 응용) 모스 코드 결정 트리

모스 부호는 아마 다들 잘 알 것이다. 점과 선의 조합으로 구성된 메시지 전달용 부호를 뜻한다.
알파벳을 모스 부호로 변환하여 그 모스 부호를 알파벳으로 다시 읽어들이는 데 이진 트리가 사용된다.

table = [('A', '.-')] # 모든 알파벳을 담기에는 귀찮으므로 그냥 A만 가지고 해보자(__)

def make_morse_tree(): # 모스 결정 트리
    root = TNode(None, None, None)
    for tp in table:
        code = tp[1]
        node = root

    for c in code:
        if c == '.':
            if node.left is None:
                node.left = TNode(None, None, None)
            node = node.left
        elif c == '-':
            if node.right is None:
                node.right = TNode(None, None, None)
            node = node.right

        node.data = tp[0]
    return root


def decode(root, code): # 여기 root에 make_morse_tree()한 거 넣어주면 됨.
    node = root
    for c in code:
        if c == '.':
            node = node.left
        elif c == '-':
            node = node.right
    return node.data

def encode(ch): # 모스 코드로의 변환은 간단히 그 알파벳에 해당하는 모스 코드의 인덱스와 연결지어주면면 된다.
    idx = ord(ch) - ord('A')
    return table[idx][1]

 

 

작성일자: 2023-03-13