어떤 이진 트리의 전위 순회(preorder traversal)와 중위… | [7급 국가직 자료구조론] 23년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 23년 1회차
어떤 이진 트리의 전위 순회(preorder traversal)와 중위 순회(inorder traversal)한 순서가 다음과 같을 때, 이 트리의 단말 노드만을 모두 나열한 것은?○ 전위 순회: A, B, D, E, C, F, G, H, I
○ 중위 순회: E, D, B, A, G, F, H, C, I
1
A, D, E
2
B, C, D, F
3
D, E, F, I
4
E, G, H, I
해설
단말 노드는 E, G, H, I이다.
전위 순회의 첫 원소 A가 루트이고, 중위 순회에서 A의 왼쪽(E, D, B)이 왼쪽 서브트리, 오른쪽(G, F, H, C, I)이 오른쪽 서브트리다. 같은 방식을 서브트리마다 재귀적으로 적용한다.
- 왼쪽 서브트리: 전위 B, D, E에서 루트 B, 중위 E, D가 모두 B의 왼쪽이므로 B의 왼쪽 자식 D, D의 왼쪽 자식 E가 된다. 단말은 E.
- 오른쪽 서브트리: 전위 C, F, G, H, I에서 루트 C, 중위에서 G, F, H는 왼쪽, I는 오른쪽이다. 다시 F를 루트로 G는 왼쪽, H는 오른쪽 자식이 된다. 단말은 G, H, I.
A, B, C, D, F는 자식이 있는 내부 노드이므로 이들이 들어간 나열은 모두 틀리다.
오류나 개정된 내용이 보이면 알려주세요