[시나공] 트리 순회, 수식 표기 변환 완전 정리

1️⃣ 트리 순회(Tree Traversal)

✅ 1. 전위 순회 (Preorder)

🔹 방문 순서

• Root → Left → Right

🔹 특징

• 루트를 가장 먼저 방문
• Prefix 수식과 동일 구조

🔹 예시 트리

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

🔹 방문 순서

👉 A B D G H I C E F J

---

✅ 2. 중위 순회 (Inorder)

🔹 방문 순서

• Left → Root → Right

🔹 특징

• 이진 탐색 트리(BST = Binary Search Tree)에서 정렬된 결과 출력
• Infix 수식과 동일 구조

🔹 방문 순서

👉 D B H G I A E C F J

---

✅ 3. 후위 순회 (Postorder)

🔹 방문 순서

• Left → Right → Root

🔹 특징

• 루트를 가장 마지막에 방문
• Postfix 수식과 동일 구조
• 계산 순서와 동일

🔹 방문 순서

👉 D H I G B E J F C A

---

2️⃣ 수식 표기법 정리

구분	연산자 위치	예시
Infix	피연산자 사이	A + B
Prefix	앞	+ A B
Postfix	뒤	A B +

---

📌 Infix 변환 전 필수 확인 (우선순위 & 결합법칙)

① 연산 우선순위

1. 괄호 ()
2. 곱셈 / 나눗셈 (* /)
3. 덧셈 / 뺄셈 (+ -)
   

👉 위에서 아래 순서로 먼저 계산


② 같은 우선순위면 왼쪽 → 오른쪽 계산 (좌결합)

• * 와 / 는 같은 우선순위
• + 와 - 도 같은 우선순위
• 같은 우선순위면 왼쪽 → 오른쪽 계산
• 이를 Left Associative(좌결합) 이라 함

---

3️⃣ Infix → Prefix 변환 방법

🔹 예제

A / B * (C + D) + E

---

🔹 1. 연산 우선순위에 따라 괄호 묶기

(((A/B)*(C+D))+E)

---

🔹 2. 연산자를 괄호 앞쪽으로 이동

+ * / A B + C D E

---

🔹 최종 Prefix

+*/AB+CDE

---

4️⃣ Infix → Postfix 변환 방법

🔹 예제

A / B * (C + D) + E

---

🔹 1. 괄호 묶기

(((A/B)*(C+D))+E)

---

🔹 2. 연산자를 괄호 뒤로 이동

A B / C D + * E +

---

🔹 최종 Postfix

AB/CD+*E+

---

5️⃣ Postfix → Infix 변환 방법

🔹 예제

ABC-/DEF+*+

---

1. 피연산자 2개를 먼저 묶는다.

🔹 먼저 ' B C - ' 부분을 묶는다.

A (BC-) / DEF+*+

---

2. 해당 연산자를 가운데 두고 괄호로 감싼다.

🔹 ' B C - ' → (B-C)

A (B-C) / DEF+*+

---

3. 이제 ' / '를 처리한다.

🔹 ' A (B-C) / ' 처리

(A/(B-C)) DEF+*+

---

🔹 다음으로 ' E F + ' 처리

(A/(B-C)) D (EF+) * +

---

🔹 ' E F + ' → (E+F)

(A/(B-C)) D (E+F) * +

---

🔹 다음 ' * ' 처리

(A/(B-C)) (D*(E+F)) +

---

🔹 마지막 ' + ' 처리

(A/(B-C)) + (D*(E+F))

---

🔹 최종 결과

A/(B-C) + D*(E+F)

---

6️⃣ Postfix 계산 방법

🔹 예제

3 4 * 5 6 * +

🔹 계산 과정

(3×4) + (5×6)
= 12 + 30
= 42

👉 연산자가 나오면 바로 앞의 두 값을 먼저 계산한다.

---

📊 시험 포인트 정리

• 거의 매년 1문제 이상 출제
• 단독 출제 또는 자료구조와 결합 출제

🔥 출제 패턴

1. 트리 순회 결과 작성
2. Infix ↔ Prefix ↔ Postfix 변환
3. Postfix 계산 문제
4. 괄호 묶기 순서 문제

---

📌 암기 핵심 요약

• Preorder = Root → Left → Right

• Inorder = Left → Root → Right

• Postorder = Left → Right → Root

• Prefix = 연산자 앞

• Postfix = 연산자 뒤

2025 시나공 퀵이지 정보처리기사 실기 단기완성
(저자: 강윤석, 김용갑, 김우경, 김종일 | 출판사: 길벗)

※ 본 글은 위 교재를 참고하여 학습 목적으로 재정리한 내용입니다.