Binary Tree
Array-based representation of a Binary Tree
Consider a complete binary tree T having n nodes where each node contains an item (value). Label the nodes of the complete binary tree T from top to bottom and from left to right 0, 1, …, n-1. Associate with T the array A where the ith entry of A is the item in the node labelled i of T, i = 0, 1, …, n-1. Figure 6.11 depicts the array representation of a Binary tree of Figure 6.16.
Given the index i of a node, we can easily and efficiently compute the index of its parent and left and right children:
Index of Parent: (i – 1)/2, Index of Left Child: 2i + 1, Index of Right Child: 2i + 2.
|
Node # |
Item |
Left child |
Right child |
|
0 |
A |
1 |
2 |
|
1 |
B |
3 |
4 |
|
2 |
C |
-1 |
-1 |
|
3 |
D |
5 |
6 |
|
4 |
E |
7 |
8 |
|
5 |
G |
-1 |
-1 |
|
6 |
H |
-1 |
-1 |
|
7 |
I |
-1 |
-1 |
|
8 |
J |
-1 |
-1 |
|
9 |
? |
? |
? |
Figure 6.11 : Array Representation of a Binary Tree
Stacks, Queues and Trees
