이진 트리

이진 트리(Binary Tree)

---

1. 이진 트리의 정의

• 이진 트리(Binary Tree): 각 노드가 최대 2개의 자식 노드를 가지는 트리.
• 특징:
  1. 각 노드의 자식 수가 0, 1, 또는 2개.
  2. 레벨 i에서의 최대 노드 수는 (2^{i-1}).
  3. 터미널 노드(자식이 없는 노드)의 수 (n_0)는 차수가 2인 노드의 수 (n_2)보다 1개 더 많음. ((n_0 = n_2 + 1)).

---

2. 주요 용어

• 루트(Root): 트리의 시작점.
• 단말 노드(Terminal Node): 자식이 없는 노드.
• 내부 노드(Internal Node): 자식이 있는 노드.
• 레벨(Level): 루트에서 특정 노드까지의 거리.
• 깊이(Depth): 트리의 최대 레벨.
• 차수(Degree): 각 노드의 자식 수.

---

3. 이진 트리의 순회

이진 트리의 순회란 각 노드를 특정 순서로 방문하는 방법을 뜻합니다. 크게 3가지 방법이 있습니다:

1. 전위 순회 (Preorder)

   • 방문 순서: 루트 → 왼쪽 → 오른쪽
   • 예: (A → B → D → H → I → E → C → F → G)

2. 중위 순회 (Inorder)

   • 방문 순서: 왼쪽 → 루트 → 오른쪽
   • 예: (H → D → I → B → E → A → F → C → G)

3. 후위 순회 (Postorder)

   • 방문 순서: 왼쪽 → 오른쪽 → 루트
   • 예: (H → I → D → E → B → F → G → C → A)

---

4. 순회와 수식 표기법의 관계

이진 트리 순회는 산술 수식 표기법과 연관이 있습니다:

순회 방식	수식 표기법	설명
전위 순회	전위 표기법 (Prefix)	연산자가 가장 먼저 나옴.
중위 순회	중위 표기법 (Infix)	연산자가 피연산자 사이에 위치.
후위 순회	후위 표기법 (Postfix)	연산자가 가장 마지막에 나옴.

---

5. 순회 예제

예제 트리

           A
         /   \
        B     C
       / \   / \
      D   E F   G
     / \
    H   I

1) 전위 순회 (Preorder):

• 방문 순서: 루트 → 왼쪽 → 오른쪽
• 결과: (A → B → D → H → I → E → C → F → G)

2) 중위 순회 (Inorder):

• 방문 순서: 왼쪽 → 루트 → 오른쪽
• 결과: (H → D → I → B → E → A → F → C → G)

3) 후위 순회 (Postorder):

• 방문 순서: 왼쪽 → 오른쪽 → 루트
• 결과: (H → I → D → E → B → F → G → C → A)

---

6. 수식 변환

이진 트리와 수식 표기법 변환의 연관성:
1. 전위 표기법 (Prefix): 연산자를 가장 먼저 위치.

• 예: (A + B) → (+AB)

2. 중위 표기법 (Infix): 연산자를 피연산자 사이에 위치.
   • 예: (A + B) → (A + B)
3. 후위 표기법 (Postfix): 연산자를 가장 마지막에 위치.
   • 예: (A + B) → (AB+)

예제 수식:

• 수식: ( (A + B) \times (C + D) )
• 전위 표기법: (\times +AB+CD)
• 중위 표기법: ((A + B) \times (C + D))
• 후위 표기법: (AB+CD+×)

---

7. 응용 및 실전 대비

• 시험 문제 유형:

  1. 이진 트리 순회를 통해 결과를 예측.
  2. 수식 변환(전위 ↔ 중위 ↔ 후위).
  3. 트리에서 특정 노드의 차수, 레벨, 깊이 등을 계산.

• 필수 암기:

  • 순회 방식(전위, 중위, 후위)의 루트 위치.
  • 수식 변환 시 연산자의 위치 이동 규칙.

---

8. 요약

1. 이진 트리는 각 노드의 자식 수가 2 이하인 구조.
2. 순회 방식(전위, 중위, 후위)은 트리 탐색의 기본.
3. 트리 순회는 산술 수식 변환과 밀접한 관련이 있음.
4. 순회 방법과 수식 표기법을 정확히 구분하는 것이 중요.

이진 트리의 순회와 수식 표기법은 데이터 구조와 알고리즘에서 자주 출제되는 영역이므로 철저히 복습하세요. 😊