[자료구조] 트리, 이진트리, 힙 - 2

[배열을 이용한 이진 트리의 표현]

이진트리의 가장 큰 특징은 자식 노드를 2개씩 가진다는 것이다. 이러면 노드 번호를 붙여서 부모, 자식 노드에 접근하기가 굉장히 편리해진다.

트리의 번호는 상->하, 왼->오의 순으로 번호가 붙는다. 루트노드를 1로 시작할 때 왼쪽 노드는 2, 오른쪽 노드는 3 이렇게 번호가 붙는다. 그렇담 이진트리의 규칙을 적용해 부모노드를 i, 왼쪽 자식 노드를 2*i, 오른쪽 자식 노드를 2*i+1라는 규칙성을 적용할 수 있다.

• 노드 번호가 i인 노드의 부모 노드 : i/2

• 노드 번호가 i인 노드의 왼쪽 자식 노드 : 2*i

• 노드 번호가 i인 노드의 오른쪽 자식 노드 : 2*i+1

위의 트리를 배열로 표현하면 저렇게 될 것이다.

그렇다면 높이가 h일 때 배열의 크기는 어떻게 설정하면 될까? 앞에서 봤던 높이가 h일때 최대 노드의 개수만큼 설정하면 된다,.

<레벨 h인 트리의 최대 개수>
$$2^{h+1}-1$$