[핵심] 컴퓨터공학개론 7단원 – 자료구조와 알고리즘: 트리(Tree) & 그래프(Graph)

1. 트리(Tree)란?

트리는 계층적인 자료구조로, 노드(Node)와 간선(Edge)으로 구성된다. 하나의 루트(Root) 노드에서 시작해 하위 노드들로 뻗어나가는 구조이다.

• 루트 노드: 가장 위에 있는 시작 노드 (부모가 없음)
• 리프 노드: 자식이 없는 말단 노드
• 서브트리: 특정 노드를 루트로 하는 하위 트리
• 이진 트리: 각 노드가 최대 두 개의 자식을 갖는 트리

2. 이진 트리의 종류

• 완전 이진 트리: 마지막 레벨을 제외하고 모든 레벨이 노드로 꽉 차 있으며, 노드는 왼쪽부터 채워진다.
• 포화 이진 트리: 모든 노드가 두 개의 자식을 가지며, 모든 레벨이 꽉 차 있음.
• 편향 이진 트리: 모든 노드가 한쪽 자식만 가진 트리 (왼쪽 또는 오른쪽으로 편향)

3. 이진 트리 순회 (Traversal)

트리의 각 노드를 특정 순서로 방문하는 방법.

• 전위 순회(Preorder): 루트 → 왼쪽 → 오른쪽
• 중위 순회(Inorder): 왼쪽 → 루트 → 오른쪽
• 후위 순회(Postorder): 왼쪽 → 오른쪽 → 루트
• 레벨 순회(Level-order): 너비 우선 탐색 방식으로 레벨 단위로 탐색

# 예시: 전위 순회
def preorder(node):
    if node:
        print(node.data)
        preorder(node.left)
        preorder(node.right)

---

4. 이진 탐색 트리 (BST)

• 왼쪽 자식 < 루트 < 오른쪽 자식의 값을 가지는 트리
• 삽입, 탐색, 삭제에 O(log n)의 시간 복잡도를 기대할 수 있음 (균형이 잘 잡혔을 경우)

5. 그래프(Graph)란?

그래프는 **노드(Vertex)**와 이들을 연결하는 **간선(Edge)**으로 구성된 자료구조이다. 관계형 데이터를 모델링할 때 유용하다.

• 무방향 그래프: 간선에 방향이 없음
• 방향 그래프: 간선에 방향이 있음
• 가중 그래프: 간선에 비용(가중치)이 부여됨
• 연결 그래프: 모든 노드가 간선을 통해 연결되어 있음

6. 그래프 표현 방식

• 인접 행렬(Adjacency Matrix): 정방행렬로 노드 간 연결 여부 표현
• 인접 리스트(Adjacency List): 노드별로 연결된 노드 목록 저장 (공간 효율적)

# 인접 리스트 예시
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A'],
    'D': ['B']
}

---

7. 그래프 탐색

깊이 우선 탐색 (DFS)

• 한 방향으로 끝까지 내려간 후, 더 이상 진행할 수 없을 때 되돌아오며 탐색
• 재귀 또는 스택 사용

def dfs(graph, v, visited):
    visited.add(v)
    print(v)
    for neighbor in graph[v]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

너비 우선 탐색 (BFS)

• 시작 노드에서 가까운 노드부터 탐색
• 큐(Queue)를 사용하여 구현

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            print(node)
            visited.add(node)
            queue.extend(graph[node])

---

8. 실습 포인트

• 트리 구조를 이해하고 순회 방식에 따라 결과가 어떻게 달라지는지 실습
• BST 삽입 및 탐색 동작 원리 익히기
• 인접 리스트를 통해 그래프 구성하고, DFS/BFS로 경로 탐색

---

9. 학습 포인트 요약

• 트리는 계층적 구조이며, 그래프는 관계형 구조를 표현하는 자료구조
• 탐색(Traversal)을 통해 트리나 그래프의 모든 노드를 방문 가능
• DFS와 BFS는 많은 알고리즘의 기반이 되는 핵심 탐색 기법
• 실습을 통해 재귀와 큐/스택의 활용 능력을 함께 향상