이진 트리(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보다 먼저 방문해야 한다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기