2025-08-12 TIL

📕오늘의 공부 주제

---

Tree의 순회(Traversal) 방법

🤔Why?

---

트리(Tree) 구조를 다루다 보면 **모든 노드를 특정 순서로 방문**해야 하는 경우가 많습니다. 예를 들어, 폴더 구조 탐색, 게임 오브젝트 계층 처리, AI 탐색 알고리즘 등이 모두 트리 순회와 관련 있습니다. 이번에 정리하면서 **DFS(깊이 우선 탐색)**와 **BFS(너비 우선 탐색)**의 차이와 구현 방법을 명확히 이해하려고 합니다.

📖오늘의 공부 내용

---

1. 트리 순회의 종류

트리 순회는 크게 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)으로 나눌 수 있습니다.

---

2. 깊이 우선 탐색(DFS: Depth-First Search)

• 한 경로를 끝까지 따라간 후, 다시 돌아와 다른 경로를 탐색.
• 순회 방식
  1. 전위 순회(Pre-order): Root → Left → Right
  2. 중위 순회(In-order): Left → Root → Right (이진 탐색 트리에서 정렬된 순서 출력)
  3. 후위 순회(Post-order): Left → Right → Root

// 전위 순회
void PreOrder(Node node)
{
    if (node == null) return;
    Console.Write(node.Value + " ");
    PreOrder(node.Left);
    PreOrder(node.Right);
}

// 중위 순회
void InOrder(Node node)
{
    if (node == null) return;
    InOrder(node.Left);
    Console.Write(node.Value + " ");
    InOrder(node.Right);
}

// 후위 순회
void PostOrder(Node node)
{
    if (node == null) return;
    PostOrder(node.Left);
    PostOrder(node.Right);
    Console.Write(node.Value + " ");
}

---

3. 너비 우선 탐색(BFS: Breadth-First Search)

• 같은 레벨(Level)의 노드를 먼저 탐색.
• 보통 Queue를 사용.

void BFS(Node root)
{
    if (root == null) return;

    Queue<Node> queue = new Queue<Node>();
    queue.Enqueue(root);

    while (queue.Count > 0)
    {
        Node node = queue.Dequeue();
        Console.Write(node.Value + " ");

        if (node.Left != null) queue.Enqueue(node.Left);
        if (node.Right != null) queue.Enqueue(node.Right);
    }
}

---

4. DFS vs BFS 비교

구분	DFS	BFS
탐색 방식	깊이 우선	너비 우선
자료구조	재귀(Stack)	Queue
메모리 사용	깊은 트리에서 스택 오버플로 위험	넓은 트리에서 메모리 사용량 많음
활용	경로 탐색, 백트래킹	최단 경로 탐색

---

5. 결론

• DFS: 깊게 파고들어 탐색 → 재귀나 스택 활용
• BFS: 레벨 단위로 탐색 → 큐 활용
• 상황에 따라 적절한 순회 방법 선택이 중요