<보기>와 같은 순회 결과들을 모두 만족하는 7개의 노드로 … | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 자료구조론] 26년 1회차
<보기>와 같은 순회 결과들을 모두 만족하는 7개의 노드로 이루어진 이진 트리의 구조로 옳은 것은?
전위 순회: A − B − D − E − F − C − G
중위 순회: D − B − F − E − A − C − G
후위 순회: D − F − E − B − G − C − A
1
2
3
4
해설

세 순회를 모두 만족하는 트리는 E의 왼쪽 자식이 F, C의 오른쪽 자식이 G인 구조이다.

전위 순회의 첫 노드 A가 루트이고, 중위 순회에서 A의 왼쪽(D B F E)이 왼쪽 서브트리, 오른쪽(C G)이 오른쪽 서브트리가 된다. 왼쪽 서브트리는 전위상 B가 루트로 D가 왼쪽, F·E가 오른쪽에 오며, 전위 E−F·중위 F−E이므로 F는 E의 왼쪽 자식이다.

오른쪽 서브트리는 전위 C−G, 중위 C−G이므로 G는 C의 오른쪽 자식이고, 후위 순회 D−F−E−B−G−C−A로도 확인된다.

  • G가 C의 왼쪽 자식인 구조는 중위 순회가 G−C 순서가 되어 맞지 않는다.
  • F가 E의 오른쪽 자식인 구조는 중위 순회가 E−F 순서가 되어 맞지 않는다.
  • E가 B의 왼쪽, D가 B의 오른쪽에 있는 구조는 전위 순회가 A−B−E−F−D… 가 되어 맞지 않는다.

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

이어서 풀어보기

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