다음은 이진트리를 후위순회(postorder traversal)와 중위… | [7급 국가직 자료구조론] 15년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 15년 1회차
다음은 이진트리를 후위순회(postorder traversal)와 중위순회(inorder traversal)로 방문한 결과이다. 이 두 가지 순회 결과를 이용하여 이진트리를 구성한 것으로 옳은 것은?Postorder 방문순서 : ADEBHGJKIFC
Inorder 방문순서 : ABDECGHFJIK
1
2
3
4
해설
두 순회로 복원한 트리는 루트 C 아래 왼쪽 B(A, E), 오른쪽 F(G, I)이고, D는 E의 왼쪽 자식, H는 G의 오른쪽 자식, J·K는 I의 양쪽 자식인 트리이다.
후위순회의 마지막 C가 루트이고, 중위순회에서 C의 왼쪽 ABDE와 오른쪽 GHFJIK가 각 서브트리가 된다. 같은 방법을 반복하면 왼쪽은 후위 ADEB에서 B가 루트, 오른쪽은 후위 HGJKIF에서 F가 루트이며, 중위순회 위치로 각 자식의 좌우가 정해진다.
- D를 A의 오른쪽 자식으로 둔 트리: 중위순회가 A, D, B, E…로 바뀌어 주어진 결과와 맞지 않는다.
- H·J를 G의 양쪽 자식으로 둔 트리: J는 중위순회에서 F 뒤에 오므로 F의 오른쪽 서브트리(I 아래)에 있어야 한다.
- H를 F의 왼쪽 자식으로 두고 G·J를 그 자식으로 둔 트리: 후위순회에서 H가 G보다 먼저 나오므로 G가 H의 부모여야 한다.
오류나 개정된 내용이 보이면 알려주세요



