이진트리를 전위순회(preorder)와 중위순회(inorder)로 방문… | [국회직 9급 컴퓨터일반] 19년 1회차 기출문제 상세 페이지
1[국회직 9급 컴퓨터일반] 19년 1회차
이진트리를 전위순회(preorder)와 중위순회(inorder)로 방문한 결과가 다음과 같다. 이 이진트리를 후위순회(postorder)로 방문한 결과는 무엇인가?전위순회 = [ABCDEFG]
중위순회 = [CBDAFGE]
1
[GFEDCBA]
2
[FEGDCBA]
3
[CBDGFEA]
4
[CDBGFEA]
5
[CDBFGEA]
해설
주어진 순회 결과로 트리를 복원하면 후위순회 결과는 [CDBGFEA]이다.
전위순회의 첫 값이 루트이고, 중위순회에서 그 루트의 왼쪽과 오른쪽이 각각 왼쪽·오른쪽 서브트리이다.
루트 A: 중위 [CBD]가 왼쪽, [FGE]가 오른쪽 서브트리이다.
왼쪽 서브트리: 전위 [BCD]이므로 루트는 B, 왼쪽 자식 C, 오른쪽 자식 D이다.
오른쪽 서브트리: 전위 [EFG]이므로 루트는 E이고, 중위 [FG]가 E의 왼쪽이다. F가 E의 왼쪽 자식, G가 F의 오른쪽 자식이다.후위순회는 왼쪽 → 오른쪽 → 루트 순이다.
왼쪽 서브트리 CDB → 오른쪽 서브트리 GFE → 루트 A
이어 붙이면 [CDBGFEA]가 된다.
오류나 개정된 내용이 보이면 알려주세요