[Data Structure] NonLinear - (1) Binary Tree

---

---

일반 트리(General Tree)

 일반적인 트리는 노드들의 집합으로, 하나의 루트 노드와 서로 겹치지 않는 여러 개의 부분 집합으로 이루어진 나머지 노드들로 구성되어 있다. 트리에서는 노드들 간에 상하관계인 부모-자식 관계가 만들어진다. 즉 부모와 자식 간의 레퍼런스가 있어 서로의 노드를 식별할 수 있다. 일반 트리는 자식 노드 수의 제한이 없기 때문에 무한정 늘어날 수 있는 특징이 있으며, 이로 인해 노드의 수를 파악하기 어려우므로 알고리즘을 적절하게 사용하기 어렵다. 따라서 주로 일반 트리를 이진 트리로 변환해 사용한다.

 

class Node:
    def __init__(self, data) -> None:
        self.data = data
        self.children = []


root = Node(1)
node1 = Node(2)
node2 = Node(3)
node3 = Node(4)
node4 = Node(5)
node5 = Node(6)
node6 = Node(7)
node7 = Node(8)
node8 = Node(9)

root.children.append(node1)
root.children.append(node2)
root.children.append(node3)
node1.children.append(node4)
node1.children.append(node5)
node1.children.append(node6)
node3.children.append(node7)
node3.children.append(node8)

 이런 식으로 각 노드의 children 속성에 자식 노드들의 레퍼런스를 설정해 일반적인 트리를 만들어낼  수 있다.

 

 

 

---

이진 트리(Binary Tree)

 이진 트리는 각 노드가 최대 2개의 자식 노드를 가질 수 있는 특징이 있다. 그러므로 임의의 노드의 두 자식 노드를 각각 왼쪽 자식, 오른쪽 자식으로 구별해 부른다.

 

 

이진 트리의 종류

 

---

(1) 정 이진 트리 (Full Binary Tree)

 모든 노드가 2개 또는 0개의 자식을 갖는 이진 트리

 

 

---

(2) 완전 이진 트리 (Complete Binary Tree)

• 마지막 레벨 직전의 레벨까지의 모든 노드들이 다 채워진 트리
• 마지막 레벨의 노드들이 왼쪽부터 오른쪽 방향으로 다 채워져 있는 트리
• 두 조건을 만족하는 트리를 완전 이진 트리라고 함

 

 완전 이진 트리에서 노드의 개수가 n일 때 높이는 lg(n)에 비례한다.

 

 

---

(3) 포화 이진 트리 (Perfect Binary Tree)

• 모든 레벨에 노드들이 빠짐없이 꽉 차있는 트리

 

높이에 따라 2의 제곱으로 노드의 개수가 늘어나므로, 노드의 개수가 n, 트리의 높이가 h일 때 n = 2^(h+1) - 1의 공식이 성립한다.

 

 

 

---

완전 이진 트리 (Complete Binary Tree)에서 탐색

 완전 이진 트리에서는 마지막 레벨 직전의 모든 노드들이 차 있고, 마지막 레벨의 노드들은 왼쪽부터 차 있다는 조건을 만족하므로 이 경우에는 특수하게 리스트를 이용해 노드를 구성하고 탐색할 수 있다.

 

def find_parent_index(index):
    if index // 2 == 0:
        return None

    return index // 2


def find_left_child_index(tree, index):
    if index * 2 >= len(tree):
        return None

    return index * 2


def find_right_child_index(tree, index):
    if index * 2 + 1 >= len(tree):
        return None

    return index * 2 + 1


complete_binary_tree = [None, 7, 13, 5, 12, 100, 4, 3, 6, 2, 8]

print(complete_binary_tree[1])

left_child = find_left_child_index(complete_binary_tree, 1)
print(complete_binary_tree[left_child])
right_child = find_right_child_index(complete_binary_tree, 1)
print(complete_binary_tree[right_child])


print(complete_binary_tree[3])

left_child = find_left_child_index(complete_binary_tree, 3)
print(complete_binary_tree[left_child])
right_child = find_right_child_index(complete_binary_tree, 3)
print(complete_binary_tree[right_child])

7
13
5

5
4
3

 리스트의 0번째 인덱스에는 None을 부여하고 그 이후로 데이터를 저장했을 때, 각 데이터의 순서가 완전 이진 트리를 왼쪽 위에서부터 차례대로 데이터를 삽입한 상태라고 할 때, 어떤 자식 노드는 (부모 노드의 인덱스) * 2 or (부모 노드의 인덱스) * 2 + 1의 인덱스를 가진다. 왼쪽의 경우는 왼쪽 자식 노드, 오른쪽의 경우는 오른쪽 자식 노드다.

 

 부모 인덱스를 찾을 경우에는 (자식 노드의 인덱스) // 2를 해주면 된다.

 

 

 

---

트리 순회 (Tree Traverse)

 트리를 순회하는 방법은 전위 순회(pre-order), 중위 순회(in-order), 후위 순회(post-order)가 있다. 기본적으로 트리를 순회할 때는 재귀 함수를 이용하며, 왼쪽 노드부터 먼저 순회한 뒤 오른쪽 노드를 순회한다.

 

 이때 노드를 언제 방문하는지에 따라 앞서 언급한 세 가지 순회 방법이 나뉜다.

 

 첫번째로 전위 순회는 재귀적으로 함수가 호출될 때 먼저 노드를 방문하고 왼쪽노드를 순회, 그리고 오른쪽 노드를 순회한다. 두번째로 중위 순회는 왼쪽 노드를 순회한 뒤에 노드를 방문하고 오른쪽 노드를 순회한다. 세번째로 후위 순회는 왼쪽 노드를 순회하고 오른쪽 노드를 순회하고 난 뒤에 노드를 방문하게 된다.

 

 말로 하면 어렵지만 코드를 보면 어렵지 않다.

 

class Node:
    """이진 트리 노드"""

    def __init__(self, data) -> None:
        self.data = data
        self.left_child = None
        self.right_child = None


def traverse_preorder(node):
    """전위 순회"""
    if node is not None:
        print(node.data)
        traverse_preorder(node.left_child)
        traverse_preorder(node.right_child)


def traverse_inorder(node):
    """중위 순회"""
    if node is not None:
        traverse_inorder(node.left_child)
        print(node.data)
        traverse_inorder(node.right_child)


def traverse_postorder(node):
    """후위 순회"""
    if node is not None:
        traverse_postorder(node.left_child)
        traverse_postorder(node.right_child)
        print(node.data)


# 여러 노드 인스턴스 생성
node_A = Node("A")
node_B = Node("B")
node_C = Node("C")
node_D = Node("D")
node_E = Node("E")
node_F = Node("F")
node_G = Node("G")
node_H = Node("H")
node_I = Node("I")

# 생성한 노드 인스턴스들 연결
node_F.left_child = node_B
node_F.right_child = node_G

node_B.left_child = node_A
node_B.right_child = node_D

node_D.left_child = node_C
node_D.right_child = node_E

node_G.right_child = node_I

node_I.left_child = node_H

# 노드 F를 root 노드로 만든다
root_node = node_F

# 만들어 놓은 트리를 in-order로 순회한다
print("전위 순회")
traverse_preorder(root_node)
print("중위 순회")
traverse_inorder(root_node)
print("후위 순회")
traverse_postorder(root_node)

전위 순회 F B A D C E G I H
중위 순회 A B C D E F G H I
후위 순회 A C E D B H I G F

 셋 다 root node부터 시작하는 것은 같다.

 

 우선 전위 순회 함수인 traverse_preorder를 보면 루트 노드가 처음에 파라미터로 들어가서 print(node.data)를 통해 곧바로 출력된다. 그다음에 왼쪽 자식 노드가 재귀적으로 호출되고 나면 다시 왼쪽 자식 노드가 곧바로 출력되고 다시 왼쪽 자식 노드를 호출한다. 이런 식으로 왼쪽 노드가 없을 때까지 호출되고 나면 오른쪽 노드를 호출하므로 오른쪽 노드가 출력되게 된다.

 

 중위 순회일 경우에는 왼쪽 노드가 없을 때까지 계속 호출한 뒤에 print(node.data)를 통해 왼쪽 끝에 있는 노드부터 출력된다.

 

 후위 순회일 경우도 비슷하게 출력된다.