이진 트리(binary tree)의 전위 순회(preorder trav… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
이진 트리(binary tree)의 전위 순회(preorder traversal)와 중위 순회(inorder traversal) 결과가 <보기>와 같을 때, 이 트리의 후위 순회(postorder traversal) 결과로 가장 옳은 것은?<보기>
전위 순회: A − B − D − E − C − F
중위 순회: D − B − E − A − C − F
1
D − B − E − C − F − A
2
D − E − B − C − F − A
3
D − E − B − F − C − A
4
E − D − B − F − C − A
해설
후위 순회 결과는 D − E − B − F − C − A이다.
전위 순회의 첫 원소 A가 루트이고, 중위 순회에서 A의 왼쪽 D, B, E가 왼쪽 서브트리, 오른쪽 C, F가 오른쪽 서브트리다.
왼쪽은 전위가 B, D, E이므로 B가 루트이고 D가 왼쪽, E가 오른쪽 자식이다. 오른쪽은 전위·중위가 모두 C, F이므로 C가 루트이고 F는 C의 오른쪽 자식이다.
- D − B − E − C − F − A: 왼쪽 서브트리를 중위 순서로 적은 것으로, 후위에서는 B가 D, E 뒤에 와야 한다.
- D − E − B − C − F − A: 오른쪽 서브트리의 루트 C가 자식 F보다 먼저 나와 후위 순서가 아니다.
- E − D − B − F − C − A: D가 왼쪽 자식이므로 E보다 먼저 방문해야 한다.
오류나 개정된 내용이 보이면 알려주세요