<보기>의 트리를 중위 스레드 이진트리로 구성하려고 한다. … | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 자료구조론] 26년 1회차
<보기>의 트리를 중위 스레드 이진트리로 구성하려고 한다. 이때 실제 자식 노드를 가리키는 링크 수를 aa, 중위 선행자 또는 중위 후속자를 가리키는 스레드 수를 bb, 스레드 구성 후에도 NULL로 남는 포인터 수를 cc라고 할 때, aa, bb, cc의 값으로 가장 옳은 것은? (단, 중위 선행자나 중위 후속자가 없는 경우 해당 스레드 포인터에는 NULL을 저장한다.)
문제 이미지
1
a=7b=6c=1a=7 \quad b=6 \quad c=1
2
a=7b=7c=2a=7 \quad b=7 \quad c=2
3
a=7b=8c=1a=7 \quad b=8 \quad c=1
4
a=9b=7c=2a=9 \quad b=7 \quad c=2
해설

중위 스레드 이진트리로 구성하면 실제 링크 7개, 스레드 7개, NULL 2개가 된다.

그림의 트리는 M, F, T, H, P, W, G, K의 8개 노드이므로 실제 자식 링크는 n−1=7n-1=7개이고, 전체 포인터 2n=162n=16개 중 빈 포인터는 16−7=916-7=9개이다.

중위 순회 순서는 F−G−H−K−M−P−T−W이다. 빈 포인터 9개는 모두 스레드 후보지만, 첫 노드 F의 왼쪽(선행자 없음)과 마지막 노드 W의 오른쪽(후속자 없음)은 NULL로 남으므로 스레드는 9−2=79-2=7개이다.

  • 스레드 6개·NULL 1개는 빈 포인터 합이 7개가 되어 전체 9개와 맞지 않는다.
  • 스레드 8개·NULL 1개는 선행자와 후속자가 모두 없는 양 끝 노드의 NULL 2개를 반영하지 못한 값이다.
  • 링크 9개는 노드 8개 트리의 간선 수 7개를 초과한다.

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

이어서 풀어보기

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