Introduction to Binary Trees - Advanced Topics in Java: Core Concepts in Data Structures - page 250

Note that the leaves are numbered from 6 to 10. If, for instance, H were the right subtree of B instead of the left, the
tree would not be “almost complete” since the leaves on the lowest level would not be “as far left as possible.”
The following array of size 10 can represent this almost complete binary tree:

T

C E G F B A N J K H

1 2 3 4 5 6 7 8 9 10

In general, if the tree is represented by an array T[1..n] , then the following holds:

• T[1] is the root.

• The left subtree of T[i] is T[2i] if 2i <= n and null otherwise.

• The right subtree of T[i] is T[2i+1] if 2i+1 <= n and null otherwise.

• The parent of T[i] is T[i/2] (integer division).

Looked at another way, there is exactly one almost complete binary tree with n nodes, and an array of size n
represents this tree.
An almost complete binary tree has no “holes” in it; there is no room to add a node in between existing nodes.
The only place to add a node is after the last one.
For instance, Figure 8-14 is not “almost complete” since there is a “hole” at the right subtree of B .

1

C

2

3

G

E

4

5 6

7

F

N

B

A

9

8 10 11 12

J K

H

L M

Figure 8-14. Empty right subtree of B makes this not “almost complete”

With the hole, the left subtree of A (in position 6) is not now in position 6*2 = 12, and the right subtree is not in
position 6*2+1 =13. This relationship holds only when the tree is almost complete.
Given an array T[1..n] representing an almost complete binary tree with n nodes, we can perform an in-order
traversal of the tree with the call inOrder(1, n) of the following function:

public static void inOrder(int h, int n) {
if (h <= n) {
inOrder(h * 2, n);
visit(h); //or visit(T[h]), if you wish
inOrder(h * 2 + 1, n);
}
} //end inOrder

We can write similar functions for pre-order and post-order traversals.