Java Reference
In-Depth Information
0
1
2
3
4
5
6
7
8
9
10
11
(A)
Position
0
1
2
3
4
5
6
7
8
9
10
11
Parent
-
0
0
1
1
2
2
3
3
4
4
5
Left Child
1
3
5
7
9
11
-
-
-
-
-
-
Right Child
2
4
6
8
10
-
-
-
-
-
-
-
Left Sibling
-
-
1
-
3
-
5
-
7
-
9
-
Right Sibling
-
2
-
4
-
6
-
8
-
10
-
-
(b)
Figure5.12
A complete binary tree and its array implementation. (a) The com-
plete binary tree with twelve nodes. Each node has been labeled with its position
in the tree. (b) The positions for the relatives of each node. A dash indicates that
the relative does not exist.
We begin by assigning numbers to the node positions in the complete binary
tree, level by level, from left to right as shown in Figure 5.12(a). An array can
store the tree's data values efficiently, placing each data value in the array position
corresponding to that node's position within the tree. Figure 5.12(b) lists the array
indices for the children, parent, and siblings of each node in Figure 5.12(a). From
Figure 5.12(b), you should see a pattern regarding the positions of a node's relatives
within the array. Simple formulas can be derived for calculating the array index for
each relative of a node r from r's index. No explicit pointers are necessary to
reach a node's left or right child. This means there is no overhead to the array
implementation if the array is selected to be of size n for a tree of n nodes.
The formulae for calculating the array indices of the various relatives of a node
are as follows. The total number of nodes in the tree is n. The index of the node in
question is r, which must fall in the range 0 to n 1.
• Parent(r) = b(r 1)=2c if r 6= 0.
• Left child(r) = 2r + 1 if 2r + 1 < n.
• Right child(r) = 2r + 2 if 2r + 2 < n.
• Left sibling(r) = r 1 if r is even.
