Tree & Graph

# Tree & Graph

> 이진 탐색 트리, DFS/BFS, 인접 행렬·리스트

## 학습 목표

- 이진 탐색 트리(BST)의 구조와 연산을 구현한다
- DFS와 BFS 순회 방식을 이해한다
- 인접 행렬과 인접 리스트로 그래프를 표현한다

## 내용

### 이진 탐색 트리

```c
typedef struct BSTNode {
    int data;
    struct BSTNode *left, *right;
} BSTNode;

BSTNode* insert(BSTNode *root, int val) {
    if (!root) {
        BSTNode *n = malloc(sizeof(BSTNode));
        n->data = val; n->left = n->right = NULL;
        return n;
    }
    if (val < root->data) root->left  = insert(root->left,  val);
    else                  root->right = insert(root->right, val);
    return root;
}
```

### DFS (중위 순회)

```c
void inorder(BSTNode *root) {
    if (!root) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}
```

### BFS (레벨 순회)

```c
// 큐를 활용한 BFS 구현 (Queue 자료구조 필요)
void bfs(BSTNode *root) {
    // enqueue root → while queue not empty → dequeue, print, enqueue children
}
```

### 인접 행렬 vs 인접 리스트

```c
// 인접 행렬
int graph[V][V];

// 인접 리스트
typedef struct AdjNode { int dest; struct AdjNode *next; } AdjNode;
AdjNode *adj[V];
```

## 참고

- BST의 평균 탐색 시간은 O(log n)이지만 편향 트리의 경우 O(n)이 된다

// COMMENTS

ON THIS PAGE