[자료구조]완전 이진 트리를 배열로 나타내기

일반적으로 leftChild와 rightChild를 통해 노드를 연결해가면서 트리를 만듭니다.

하지만 이 완전 이진 트리를 배열 형태로 나타낼 수 있습니다.

 

완전 이진 트리

위와 같은 완전 이진 트리 있다고 가정합시다.

위 이진 트리에는 12개의 노드가 있습니다.

충분한 크기의 배열이 있다고 가정합시다.

 

1. root 노드인 노드 A의 값을 1번째 인덱스에 넣습니다.
2. 노드 A의 leftChild인 노드 B의 값을 2번째 인덱스에 넣습니다.
3. 노드 A의 rightChild인 노드 C의 값을 3번째 인덱스에 넣습니다.
4. 그 다음, 노드 B의 leftChild인 노드 D의 값을 4번째 인덱스에 넣습니다.

이런 식으로, level이 낮은 노드부터, level이 같다면 왼쪽에 있는 노드부터 차례대로 배열에 넣습니다.

여기에는 한 가지 규칙이 있습니다.

i번째 인덱스에 저장되는 노드의 leftChild는 (2*i)번째 인덱스에 저장되고, rightChild는 (2*i+1)번째 인덱스에 저장됩니다.

예를 들어, 4번째 인덱스에 엤는 노드 D의 rightChild인 노드 I는 9번째 인덱스에 있겠죠?

이러한 규칙으로 위 완전 이진 트리를 배열로 나타내면 아래와 같습니다.

 

index	node
0	-
1	A
2	B
3	C
4	D
5	E
6	F
7	G
8	H
9	I
10	J
11	K
12	L

 

만약 완전 이진 트리의 노드가 n개라면 (n+1)짜리 배열을 만들어 1부터 저장하면 됩니다.