이진 트리 (Binary Tree)

이진 트리(Binary Tree)는 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조이다. 이진 트리는 트리 자료 구조의 한 종류로, 그 구조적 특성과 다양한 응용으로 인해 컴퓨터 과학에서 매우 중요한 역할을 한다.

기본 개념

• 노드 (Node): 트리의 기본 구성 요소로, 각 노드는 데이터를 저장한다.
• 루트 (Root): 트리의 최상위 노드이다. 트리는 하나의 루트 노드를 가진다.
• 부모 (Parent) 노드: 다른 노드를 가리키는 노드를 의미한다.
• 자식 (Child) 노드: 다른 노드로부터 가리켜지는 노드를 의미한다.
• 왼쪽 자식 (Left Child)와 오른쪽 자식 (Right Child): 각 노드는 최대 두 개의 자식 노드를 가지며, 왼쪽 자식과 오른쪽 자식으로 구분된다.
• 리프 (Leaf) 노드: 자식 노드를 가지지 않는 노드이다.
• 깊이 (Depth): 루트 노드에서 특정 노드까지의 경로 길이이다.
• 높이 (Height): 특정 노드에서 가장 깊은 리프 노드까지의 경로 길이이다.

이진 트리의 종류

1. 완전 이진 트리 (Complete Binary Tree):
   • 모든 레벨이 꽉 차 있으며, 마지막 레벨은 왼쪽부터 순서대로 채워진다.
2. 포화 이진 트리 (Full Binary Tree):
   • 모든 노드가 0개 또는 2개의 자식 노드를 가진다.
3. 균형 이진 트리 (Balanced Binary Tree):
   • 트리의 높이가 최소화되도록 균형을 맞춘 트리이다. AVL 트리와 레드-블랙 트리가 대표적이다.
4. 이진 탐색 트리 (Binary Search Tree):
   • 각 노드의 왼쪽 서브트리는 그 노드보다 작은 값을 가지며, 오른쪽 서브트리는 그 노드보다 큰 값을 가진다.

이진 트리의 순회 방법

이진 트리의 순회는 트리의 모든 노드를 특정한 순서로 방문하는 방법을 말한다. 주요 순회 방법은 다음과 같다:

1. 전위 순회 (Preorder Traversal):
   • 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순서로 방문한다.
   • 순서: Root, Left, Right
2. 중위 순회 (Inorder Traversal):
   • 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순서로 방문한다.
   • 순서: Left, Root, Right
   • 이진 탐색 트리에서 중위 순회를 하면 노드 값이 오름차순으로 정렬된다.
3. 후위 순회 (Postorder Traversal):
   • 왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트 순서로 방문한다.
   • 순서: Left, Right, Root
4. 레벨 순회 (Level Order Traversal):
   • 루트에서부터 레벨별로 왼쪽에서 오른쪽 순서로 방문한다. 주로 큐를 사용하여 구현한다.

from collections import deque

class Node:
    def __init__(self, key) -> None:
        self.left = None
        self.right = None
        self.val = key

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

    def insert(self, key) -> None:
        new_node = Node(key)
        if self.root is None:
            self.root = new_node
        else:
            self._insert(self.root, key)

    def _insert(self, root, key) -> None:
        if key < root.val:
            if root.left is None:
                root.left = Node(key)
            else:
                self._insert(root.left, key)
        else:
            if root.right is None:
                root.right = Node(key)
            else:
                self._insert(root.right, key)

    def preorder(self, node):
        if node:
            print(node.val, end=" ")
            self.preorder(node.left)
            self.preorder(node.right)

    def inorder(self, node):
        if node:
            self.inorder(node.left)
            print(node.val, end=" ")
            self.inorder(node.right)

    def postorder(self, node):
        if node:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.val, end=" ")

    def level_order(self):
        if self.root is None:
            return
        q = deque()
        q.append(self.root)
        while q:
            cur = q.popleft()
            print(cur.val, end=" ")
            if cur.left:
                q.append(cur.left)
            if cur.right:
                q.append(cur.right)

bt = BinaryTree()
bt.insert(10)
bt.insert(5)
bt.insert(15)
bt.insert(2)
bt.insert(7)
bt.insert(12)
bt.insert(18)

print("Preorder traversal:")
bt.preorder(bt.root)  # Output: 10 5 2 7 15 12 18

print("\\nInorder traversal:")
bt.inorder(bt.root)  # Output: 2 5 7 10 12 15 18

print("\\nPostorder traversal:")
bt.postorder(bt.root)  # Output: 2 7 5 12 18 15 10

print("\\nLevel order traversal:")
bt.level_order()  # Output: 10 5 15 2 7 12 18

주요 구현 설명

1. Node 클래스:
   • 각 노드는 데이터를 저장하며, 왼쪽과 오른쪽 자식 노드를 가리키는 포인터를 가진다.
2. BinaryTree 클래스:
   • 이진 트리의 루트를 초기화한다.
   • insert 메서드는 새로운 노드를 트리에 삽입한다.
   • preorder, inorder, postorder 메서드는 전위, 중위, 후위 순회를 수행한다.
   • level_order 메서드는 레벨 순회를 수행한다.

이진 트리의 응용

이진 트리는 다양한 알고리즘과 데이터 구조의 기초가 된다.

1. 이진 탐색 트리 (Binary Search Tree): 데이터의 삽입, 삭제, 검색을 효율적으로 수행한다.
2. 힙 (Heap): 우선순위 큐를 구현하는 데 사용된다.
3. 트라이 (Trie): 문자열 검색과 관련된 응용 프로그램에서 사용된다.
4. 압축 알고리즘: 허프만 코딩과 같은 데이터 압축 알고리즘에서 사용된다.
5. 파싱 트리: 구문 분석(파싱)에서 구문 트리를 나타내는 데 사용된다.

이진 트리는 그 구조적 특성과 다양한 순회 방법 덕분에 컴퓨터 과학의 많은 영역에서 널리 사용된다.

 

모든 코드는 github에 저장되어 있습니다.

https://github.com/SeongUk18/Algorithm/tree/main/Data_structure_algorithms