완전 이진트리(complete binary tree)를 배열에 저장할 … | [7급 국가직 자료구조론] 13년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 13년 1회차
완전 이진트리(complete binary tree)를 배열에 저장할 때, 루트 노드를 배열 A[1]에 저장하고 나머지 노드들은 트리의 레벨순서에 따라 왼쪽에서 오른쪽으로 연속적으로 저장한다. 노드 A[k]와 관계된 노드를 찾는 규칙이 바르게 짝지어지지 않은 것은?
1
부모 노드 - A[⌊k/2⌋]
2
왼쪽 자식 노드 - A[2k]
3
오른쪽 자식 노드 - A[2k+1]
4
형제 노드 - A[k+1]
해설
형제 노드를 항상 A[k+1]로 찾는 규칙은 틀렸다.
k가 짝수면 왼쪽 자식이라 형제가 A[k+1]이지만, k가 홀수면 오른쪽 자식이라 형제는 A[k−1]이다(루트는 형제가 없다).
- 부모 노드 − A[⌊k/2⌋]: 자식 2k와 2k+1을 2로 나눈 몫이 모두 k이므로 옳다.
- 왼쪽 자식 노드 − A[2k]: 레벨순서 연속 저장의 정의대로 옳다.
- 오른쪽 자식 노드 − A[2k+1]: 왼쪽 자식 바로 다음 칸이므로 옳다.
오류나 개정된 내용이 보이면 알려주세요