The sequential representation uses an array to store information corresponding to each node of a tree. Consider the binary tree shown in Figure 7.9. Its depth is 5 and it has fourteen nodes. The nodes are numbered in a special way. This numbering may be obtained by preorder traversing the tree and, as each node is accessed, assigning it a node number. The root is assigned 1, each left successor of a node is assigned twice the number of its predecessor, and each right successor is assigned one more than twice the number of its predecessor. With nodes numbered in this way, the predecessor of node i is numbered i/2 (integer divide), its left successor is numbered 2*i, and its right successor 2*i+1.
The sequential representation of a binary tree is obtained by storing the record corresponding to node i of the tree as the ith record in an array of records, as shown in Figure 7.9. A node not in the tree can be recognized by a special value in its corresponding array position (such as node 8, which has - as its value) or by a node number (like 24) that exceeds the highest node number in the tree (20 in this example). Given a pointer p to a node in the array, it is easy to determine the position of its predecessor (p/2), its left successor (2*p), and its right successor (2*p+1).
A binary tree with n nodes will require an array length between n and 2n - 1. The smallest length (n) is sufficient when the binary tree is complete, and the greatest length (2n - 1) corresponds to the case of an extremely skewed binary tree whose nodes have only right successors. No space in the array is unused for a complete binary tree, and the array length is proportional to the number of nodes in the tree. However, a sparse tree can waste a great deal of array space. The worst case requires 2n - 1 positions but uses only n. Thus the sequential representation is convenient for dealing with complete static binary trees. Such trees arise, for example, when you must put student records in alphabetical order by student name. How to do such ordering is considered in the next chapter (Section 8.4). For cases when the tree may change size or shape drastically, the sequential representation is not appropriate. An example of this situation is found in the integer or word counting problem of Section 7.1.