어떤 이진 트리(binary tree)를 전위 순회(preorder t… | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 08년 1회차
어떤 이진 트리(binary tree)를 전위 순회(preorder traversal)한 결과는 1, 2, 3, 4, 5, 6, 7, 8, 9이고, 중위 순회(inorder traversal)한 결과는 2, 3, 1, 5, 4, 7, 8, 6, 9라고 할 때, 이 이진 트리는?
1
2
3
4
해설

복원한 트리는 루트 1의 왼쪽에 2와 그 오른쪽 자식 3, 오른쪽에 4(왼쪽 5, 오른쪽 6)가 있고, 6의 왼쪽 자식 7의 오른쪽 자식이 8, 6의 오른쪽 자식이 9인 형태이다.

전위 순회의 첫 원소가 루트이고, 중위 순회에서 루트의 왼쪽은 왼쪽 서브트리, 오른쪽은 오른쪽 서브트리이다. 1을 기준으로 {2, 3}과 {5, 4, 7, 8, 6, 9}로 나누고, 같은 방식으로 4와 6을 서브트리의 루트로 재귀 분할한다.

  • 3이 2의 왼쪽 자식이고 8 아래에 9가 달린 트리: 중위 순회가 3, 2로 시작해 주어진 2, 3과 어긋난다.
  • 3이 2의 오른쪽 자식이고 9가 7의 자식, 8이 6의 오른쪽 자식인 트리: 전위 순회가 6, 7, 9, 8 순이 되어 주어진 6, 7, 8, 9와 다르다.
  • 3이 2의 왼쪽 자식이고 9가 7의 자식인 트리: 중위 순회가 3, 2로 시작하고 9, 8의 위치도 주어진 순서와 맞지 않는다.

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

이어서 풀어보기

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