<보기>의 트리를 중위 스레드 이진트리로 구성하려고 한다. … | [7급 서울시 자료구조론] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 자료구조론] 26년 1회차
<보기>의 트리를 중위 스레드 이진트리로 구성하려고 한다. 이때 실제 자식 노드를 가리키는 링크 수를 , 중위 선행자 또는 중위 후속자를 가리키는 스레드 수를 , 스레드 구성 후에도 NULL로 남는 포인터 수를 라고 할 때, , , 의 값으로 가장 옳은 것은? (단, 중위 선행자나 중위 후속자가 없는 경우 해당 스레드 포인터에는 NULL을 저장한다.)
1
2
3
4
해설
중위 스레드 이진트리로 구성하면 실제 링크 7개, 스레드 7개, NULL 2개가 된다.
그림의 트리는 M, F, T, H, P, W, G, K의 8개 노드이므로 실제 자식 링크는 개이고, 전체 포인터 개 중 빈 포인터는 개이다.
중위 순회 순서는 F−G−H−K−M−P−T−W이다. 빈 포인터 9개는 모두 스레드 후보지만, 첫 노드 F의 왼쪽(선행자 없음)과 마지막 노드 W의 오른쪽(후속자 없음)은 NULL로 남으므로 스레드는 개이다.
- 스레드 6개·NULL 1개는 빈 포인터 합이 7개가 되어 전체 9개와 맞지 않는다.
- 스레드 8개·NULL 1개는 선행자와 후속자가 모두 없는 양 끝 노드의 NULL 2개를 반영하지 못한 값이다.
- 링크 9개는 노드 8개 트리의 간선 수 7개를 초과한다.
오류나 개정된 내용이 보이면 알려주세요
