🚀 트리 순회(Tree Traversal) 방법 : 후위, 전위, 중위, 레벨

---

🌳 트리(Tree)란?

"나무처럼 생긴 자료 구조!"
부모 노드와 자식 노드가 있는 계층적인 구조!

예제 트리

        A
       / \
      B   C
     / \   \
    D   E   F

• A: 루트 노드 (Root)
• B, C: A의 자식 노드 (Child)
• D, E, F: 리프 노드 (Leaf, 마지막 노드)

---

🔹 트리 순회의 종류 (4가지)

트리에서 모든 노드를 방문하는 방법에는 4가지가 있어!
✅ 전위순회(Preorder)
✅ 중위순회(Inorder)
✅ 후위순회(Postorder)
✅ 레벨순회(Level-order)

---

1️⃣ 전위 순회 (Preorder)

"부모 → 왼쪽 → 오른쪽"
Root → Left → Right

✅ 방문 순서:

A → B → D → E → C → F

✅ 설명:

• A를 먼저 방문!
• B를 방문한 후, B의 자식들(D, E) 방문
• C를 방문한 후, C의 자식(F) 방문

🎯 재귀 코드

void Preorder(Node* root) 
{
    if (root == nullptr) return;
    cout << root->data << " ";  // 1️⃣ 부모 방문
    Preorder(root->left);       // 2️⃣ 왼쪽 방문
    Preorder(root->right);      // 3️⃣ 오른쪽 방문
}

---

2️⃣ 중위 순회 (Inorder)

"왼쪽 → 부모 → 오른쪽"
Left → Root → Right

✅ 방문 순서:

D → B → E → A → C → F

✅ 설명:

• 왼쪽부터 끝까지 내려가서 D 방문
• D의 부모(B) 방문 → E 방문
• A 방문 후, C와 F 방문

🎯 재귀 코드

void Inorder(Node* root) {
    if (root == nullptr) return;
    Inorder(root->left);        // 1️⃣ 왼쪽 방문
    cout << root->data << " ";  // 2️⃣ 부모 방문
    Inorder(root->right);       // 3️⃣ 오른쪽 방문
}

---

3️⃣ 후위 순회 (Postorder)

"왼쪽 → 오른쪽 → 부모"
Left → Right → Root

✅ 방문 순서:

D → E → B → F → C → A

✅ 설명:

• 왼쪽, 오른쪽 자식들을 모두 방문한 후, 부모 방문!
• D 방문 → E 방문 → B 방문
• F 방문 → C 방문 → A 방문 (맨 마지막!)

🎯 재귀 코드

void Postorder(Node* root) {
    if (root == nullptr) return;
    Postorder(root->left);      // 1️⃣ 왼쪽 방문
    Postorder(root->right);     // 2️⃣ 오른쪽 방문
    cout << root->data << " ";  // 3️⃣ 부모 방문
}

---

4️⃣ 레벨 순회 (Level-order)

"위에서 아래로, 왼쪽에서 오른쪽으로"
BFS 방식 사용 (큐 활용!)

✅ 방문 순서:

A → B → C → D → E → F

✅ 설명:

• 한 층씩 내려가면서 방문!
• A → B, C → D, E, F 순서

🎯 큐(Queue)를 사용한 코드

void LevelOrder(Node* root) {
    if (root == nullptr) return;
    queue<Node*> q;
    q.push(root);

    while (!q.empty()) {
        Node* curr = q.front();
        q.pop();
        cout << curr->data << " ";  // 1️⃣ 현재 노드 방문

        if (curr->left) q.push(curr->left);   // 2️⃣ 왼쪽 자식 추가
        if (curr->right) q.push(curr->right); // 3️⃣ 오른쪽 자식 추가
    }
}

---

🚀 4가지 트리 순회 비교

순회 방법 순서 (예제 트리 A - B - C - D - E - F)

전위 순회 (Preorder)	A → B → D → E → C → F
중위 순회 (Inorder)	D → B → E → A → C → F
후위 순회 (Postorder)	D → E → B → F → C → A
레벨 순회 (Level-order)	A → B → C → D → E → F

---

🚀 한 줄 정리

순회 방법 방문 순서

전위순회 (Preorder)	부모 → 왼쪽 → 오른쪽
중위순회 (Inorder)	왼쪽 → 부모 → 오른쪽
후위순회 (Postorder)	왼쪽 → 오른쪽 → 부모
레벨순회 (Level-order)	위에서 아래로, 왼쪽에서 오른쪽

---

✅ 쉽게 이해하는 비유

순회 방식 현실 예제

전위 순회 (Preorder)	"집을 방문할 때, 먼저 부모(집 주인)를 만나고, 방을 방문하는 것!"
중위 순회 (Inorder)	"방(왼쪽)을 먼저 본 다음, 집 주인(부모)과 이야기하고, 나머지 방(오른쪽)을 보는 것!"
후위 순회 (Postorder)	"방을 다 보고 나서, 마지막에 집 주인(부모)과 이야기하는 것!"
레벨 순회 (Level-order)	"건물 층별로 올라가면서 모든 방을 방문하는 것!"

---

🚀 결론

"최단 거리 탐색(한 층씩 탐색)에는 레벨 순회(BFS), 깊이 탐색에는 DFS(전위, 중위, 후위)" 🚀