[자료구조] Week 6: 트리 I - 트리의 개념과 이진 트리

Day 1: 트리의 기본 개념과 용어

• 강의 내용:
  • 트리의 정의와 특징
    • 트리 구조의 개념
    • 트리의 용도와 필요성
  • 트리의 기본 용어
    • 루트, 노드, 간선, 리프, 깊이, 높이, 서브트리 등
  • 트리와 그래프의 차이
• 실습:
  • 트리의 기본 용어와 개념을 시각적으로 설명

# 트리의 기본 용어 설명
# - 루트(Root): 트리의 최상단 노드
# - 노드(Node): 트리를 구성하는 기본 요소
# - 간선(Edge): 노드와 노드를 연결하는 선
# - 리프(Leaf): 자식 노드가 없는 노드
# - 깊이(Depth): 루트 노드에서 특정 노드까지의 경로 길이
# - 높이(Height): 트리의 최대 깊이
# - 서브트리(Subtree): 트리의 부분 집합

# 트리의 예시를 시각적으로 설명
# 예: 
#         A
#       /   \
#      B     C
#     / \   / \
#    D   E F   G

 

Day 2: 이진 트리의 개념

• 강의 내용:
  • 이진 트리의 정의와 특징
    • 이진 트리의 개념
    • 이진 트리의 구조적 특징
  • 이진 트리의 종류
    • 포화 이진 트리, 완전 이진 트리, 균형 이진 트리
• 실습:
  • 이진 트리의 구조와 종류를 시각적으로 설명

# 이진 트리의 기본 용어 설명
# - 이진 트리: 각 노드가 최대 두 개의 자식 노드를 가지는 트리
# - 포화 이진 트리: 모든 레벨이 완전히 채워진 이진 트리
# - 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 완전히 채워진 이진 트리
# - 균형 이진 트리: 모든 리프 노드의 깊이 차이가 최대 1인 이진 트리

# 이진 트리의 예시를 시각적으로 설명
# 포화 이진 트리 예:
#         A
#       /   \
#      B     C
#     / \   / \
#    D   E F   G

# 완전 이진 트리 예:
#         A
#       /   \
#      B     C
#     / \   /
#    D   E F

# 균형 이진 트리 예:
#         A
#       /   \
#      B     C
#     / \     \
#    D   E     F

 

Day 3: 이진 트리의 구현

• 강의 내용:
  • 이진 트리 노드의 정의
  • 이진 트리의 삽입 연산
• 실습:
  • 이진 트리의 노드 정의 및 삽입 연산 구현

# 이진 트리 노드 클래스 정의
class TreeNode:
    def __init__(self, key):
        self.left = None
        self.right = None
        self.val = key

# 이진 트리 삽입 함수 정의
def insert(root, key):
    if root is None:
        return TreeNode(key)
    else:
        if root.val < key:
            root.right = insert(root.right, key)
        else:
            root.left = insert(root.left, key)
    return root

# 이진 트리 삽입 예제
root = TreeNode(10)
root = insert(root, 5)
root = insert(root, 20)
root = insert(root, 3)
root = insert(root, 7)
root = insert(root, 15)
root = insert(root, 25)

# 이진 트리 구조 출력 함수 (전위 순회)
def print_tree_preorder(root):
    if root:
        print(root.val, end=' ')
        print_tree_preorder(root.left)
        print_tree_preorder(root.right)

print("전위 순회 결과:")
print_tree_preorder(root)  # 10 5 3 7 20 15 25

 

Day 4: 이진 트리의 탐색과 삭제

• 강의 내용:
  • 이진 트리의 탐색 연산
  • 이진 트리의 삭제 연산
    • 노드 삭제 시 경우의 수
• 실습:
  • 이진 트리의 탐색 및 삭제 연산 구현

# 이진 트리 탐색 함수 정의
def search(root, key):
    if root is None or root.val == key:
        return root
    if root.val < key:
        return search(root.right, key)
    return search(root.left, key)

# 이진 트리 탐색 예제
print("노드 15 탐색 결과:", search(root, 15))  # 노드 15 탐색 결과: <__main__.TreeNode object at 0x...>

# 이진 트리 삭제 함수 정의
def delete_node(root, key):
    if root is None:
        return root

    if key < root.val:
        root.left = delete_node(root.left, key)
    elif key > root.val:
        root.right = delete_node(root.right, key)
    else:
        if root.left is None:
            return root.right
        elif root.right is None:
            return root.left

        temp = min_value_node(root.right)
        root.val = temp.val
        root.right = delete_node(root.right, temp.val)

    return root

def min_value_node(node):
    current = node
    while current.left is not None:
        current = current.left
    return current

# 이진 트리 삭제 예제
root = delete_node(root, 20)
print("노드 20 삭제 후 전위 순회 결과:")
print_tree_preorder(root)  # 10 5 3 7 25 15

 

Day 5: 이진 트리의 순회

• 강의 내용:
  • 이진 트리 순회의 종류
    • 전위 순회 (Preorder Traversal)
    • 중위 순회 (Inorder Traversal)
    • 후위 순회 (Postorder Traversal)
    • 레벨 순회 (Level Order Traversal)
• 실습:
  • 이진 트리 순회 방법 구현 및 예제

# 전위 순회 (Preorder Traversal)
def preorder(root):
    if root:
        print(root.val, end=' ')
        preorder(root.left)
        preorder(root.right)

# 중위 순회 (Inorder Traversal)
def inorder(root):
    if root:
        inorder(root.left)
        print(root.val, end=' ')
        inorder(root.right)

# 후위 순회 (Postorder Traversal)
def postorder(root):
    if root:
        postorder(root.left)
        postorder(root.right)
        print(root.val, end=' ')

# 레벨 순회 (Level Order Traversal)
def level_order(root):
    if root is None:
        return
    queue = []
    queue.append(root)
    while queue:
        node = queue.pop(0)
        print(node.val, end=' ')
        if node.left:
            queue.append(node.left)
        if node.right:
            queue.append(node.right)

# 순회 예제
print("전위 순회:")
preorder(root)  # 10 5 3 7 25 15

print("\n중위 순회:")
inorder(root)  # 3 5 7 10 15 25

print("\n후위 순회:")
postorder(root)  # 3 7 5 15 25 10

print("\n레벨 순회:")
level_order(root)  # 10 5 25 3 7 15

 

Day 6: 이진 트리의 응용

• 강의 내용:
  • 이진 트리의 응용 사례
    • 표현식 트리
    • 결정 트리
  • 이진 트리를 사용한 알고리즘
    • 이진 탐색
    • 최소 공통 조상 찾기
• 실습:
  • 이진 탐색 알고리즘 구현

# 이진 탐색 트리에서 최소 공통 조상 찾기
def lowest_common_ancestor(root, p, q):
    while root:
        if root.val > p and root.val > q:
            root = root.left
        elif root.val < p and root.val < q:
            root = root.right
        else:
            return root
    return None

# 최소 공통 조상 예제
root = TreeNode(20)
root = insert(root, 10)
root = insert(root, 30)
root = insert(root, 5)
root = insert(root, 15)
root = insert(root, 25)
root = insert(root, 35)

lca = lowest_common_ancestor(root, 5, 15)
print("노드 5와 15의 최소 공통 조상:", lca.val)  # 10

 

Day 7: 종합 연습 및 프로젝트

• 강의 내용:
  • 이진 트리를 사용한 종합 연습 문제 풀이
    • 다양한 이진 트리 관련 문제
    • Q&A 세션
  • 미니 프로젝트
    • 이진 트리를 활용한 간단한 프로그램 구현
    • 예: 표현식 트리 평가기
• 실습:
  • 종합 연습 문제 풀기
  • 미니 프로젝트 작성 및 발표

# 연습 문제 1: 이진 탐색 트리에서 k번째 최소값 찾기
def kth_smallest(root, k):
    stack = []
    while True:
        while root:
            stack.append(root)
            root = root.left
        root = stack.pop()
        k -= 1
        if k == 0:
            return root.val
        root = root.right

# k번째 최소값 찾기 예제
root = TreeNode(20)
root = insert(root, 10)
root = insert(root, 30)
root = insert(root, 5)
root = insert(root, 15)
root = insert(root, 25)
root = insert(root, 35)

print("2번째 최소값:", kth_smallest(root, 2))  # 10

# 미니 프로젝트 예제: 표현식 트리 평가기
class ExpressionTreeNode:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

def evaluate_expression_tree(node):
    if node is None:
        return 0
    if node.left is None and node.right is None:
        return int(node.value)
    left_val = evaluate_expression_tree(node.left)
    right_val = evaluate_expression_tree(node.right)
    if node.value == '+':
        return left_val + right_val
    elif node.value == '-':
        return left_val - right_val
    elif node.value == '*':
        return left_val * right_val
    elif node.value == '/':
        return left_val / right_val

# 표현식 트리 구성 예제
root = ExpressionTreeNode('*')
root.left = ExpressionTreeNode('+')
root.right = ExpressionTreeNode('+')
root.left.left = ExpressionTreeNode('3')
root.left.right = ExpressionTreeNode('2')
root.right.left = ExpressionTreeNode('4')
root.right.right = ExpressionTreeNode('5')

# 표현식 트리 평가
print("표현식 트리 평가 결과:", evaluate_expression_tree(root))  # 45

 

이 강의는 파이썬의 자료구조 중 트리, 특히 이진 트리를 익히는 것을 목표로 하며, 각 강의는 이론과 실습을 포함합니다. 다음 주차에 대한 상세 강의를 원하시면 말씀해 주세요!