2019년 1회 정보처리기사 기출문제 10번

10. 다음 트리를 후위 순회(Postorder Traversal)한 결과는?

    ① A B D C E F                 ② D B A E C F

    ③ A B C D E F                 ❹ D B E F C A

 

 

이 문제는 이진 트리(Binary Tree)의 **후위 순회(Postorder Traversal)**에 관한 문제입니다.
정보처리기사에서 자주 출제되는 중요한 개념이니 쉽게 이해할 수 있도록 차근차근 설명드릴게요!

---

✅ 후위 순회(Postorder Traversal)란?

왼쪽 → 오른쪽 → 루트 순서로 노드를 방문하는 순회 방법입니다.

즉, 어떤 노드를 방문하기 전에 왼쪽 자식 → 오른쪽 자식을 먼저 방문하고, 마지막에 부모 노드를 방문합니다.

---

📌 주어진 트리 구조 다시 보기

        A
       / \
      B   C
     /   / \
    D   E   F

---

✅ 순서대로 방문해보기 (후위 순회: 왼쪽 → 오른쪽 → 루트)

노드 설명

D	B의 왼쪽 자식, 리프노드라 먼저 방문
B	D 다음에 자기 자신(B) 방문
E	C의 왼쪽 자식
F	C의 오른쪽 자식
C	자식들(E, F) 방문 후 C 방문
A	마지막 루트 방문

---

✅ 순서 정리 표

단계 방문 노드 설명

1	D	B의 왼쪽 자식
2	B	왼쪽(D) 방문 후 자기 자신
3	E	C의 왼쪽 자식
4	F	C의 오른쪽 자식
5	C	자식들 방문 후 자기 자신
6	A	마지막 루트

✅ 결과: D → B → E → F → C → A

---

🔍 정답 확인

❹ D B E F C A ✅

---

🧠 핵심 정리

순회 방식 순서

전위 순회 (Preorder)	루트 → 왼쪽 → 오른쪽
중위 순회 (Inorder)	왼쪽 → 루트 → 오른쪽
후위 순회 (Postorder)	왼쪽 → 오른쪽 → 루트

---

📝 결론

• 이 문제는 후위 순회 개념을 알고 있다면 쉽게 풀 수 있어요.
• 항상 순서: 왼 → 오 → 루트를 기억하세요!
• 정답은 ❹ D B E F C A입니다.