[정보처리기사 실기] 트리 순회

Question

다음은 이진 탐색 트리에서 노드를 삭제하는 과정입니다.

초기 트리: 50 /
30 70 / \ /
20 40 60 80 / 10

위 트리에서 노드 30을 삭제한 후, 후위 순회(Postorder Traversal)한 결과를 쓰시오.

※ 삭제 시 중위 후속자(inorder successor)로 대체하는 방식을 사용합니다.

Accepted Answer

10 20 40 60 80 70 50 — 노드 30을 삭제할 때 중위 후속자인 40으로 대체됩니다. 삭제 후 트리는:
        50
       /  \
      40   70
     /    / \
    20   60 80
   /
  10

후위 순회는 왼쪽→오른쪽→루트 순서로 방문합니다:
1. 40의 왼쪽 서브트리: 20의 왼쪽 10 → 20
2. 40 (루트)
3. 70의 왼쪽 60 → 오른쪽 80 → 70
4. 최종 루트 50

따라서 10 → 20 → 40 → 60 → 80 → 70 → 50 순입니다.

정보처리기사 실기 트리 순회 기출문제 #3149