다음은 어떤 일반 트리를 이진 트리로 변환한 후의 모습이다. 이에 대한… | [7급 국가직 자료구조론] 14년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 14년 1회차
다음은 어떤 일반 트리를 이진 트리로 변환한 후의 모습이다. 이에 대한 설명으로 옳은 것은? (단, 일반 트리를 이진 트리로 변환할 때, 이진 트리의 왼쪽 노드는 일반 트리의 자식(child) 중에 하나를 가리키기 위해 사용되며, 이진 트리의 오른쪽 노드는 일반 트리의 형제(sibling)들을 연결하기 위해 사용된다)
1
일반 트리에서 B의 자식 노드 개수는 2개이다.
2
일반 트리에서 C의 부모 노드는 B이다.
3
일반 트리에서 노드 D에서 J까지 경로 길이는 4이다.
4
일반 트리에서 단말 노드 개수는 7개이다.
해설
원래 일반 트리의 단말 노드는 I, E, F, J, K, L, M의 7개이다.
왼쪽 링크는 첫 자식, 오른쪽 링크는 다음 형제이므로 복원하면 A의 자식은 B, C이고, B의 자식은 D, E, F, D의 자식은 I이다. C의 자식은 G, H, G의 자식은 J, K, L, H의 자식은 M이다.
- B의 자식은 D, E, F로 3개이므로 2개라는 설명은 틀렸다.
- C는 B의 오른쪽(형제) 링크에 있으므로 부모는 B가 아니라 A이다.
- D에서 J까지의 경로는 D-B-A-C-G-J로 길이가 5이므로 4라는 설명은 틀렸다.
오류나 개정된 내용이 보이면 알려주세요
