< Free Open Study > |
Our discussion of the implementation of binary trees has so far remained limited to a scheme in which the pointers from parent to children are explicit in the data structure. That is, a member was declared in each node for the pointer to the left child and the pointer to the right child.
A binary tree can be stored in an array in such a way that the relationships in the tree are not physically represented by link members, but rather are implicit in the algorithms that manipulate the tree stored in the array. The code is, of course, much less self-documenting, but we might save memory space because we have no pointers.
Let's take a binary tree and store it in an array in such a way that we do not lose the parent-child relationships. We store the tree elements in the array, level by level, left to right. If the number of nodes in the tree is numElements, we can package the array and numElements into a struct as illustrated in Figure 8.21. The tree elements are stored with the root in tree.nodes [0] and the last node in tree.nodes[numElements - 1].
To implement the algorithms that manipulate the tree, we must be able to find the left and right child of a node in the tree. Comparing the tree and the array in Figure 8.21, we see that
tree.nodes [0]'s children are in tree.nodes [1] and tree.nodes [2].
tree.nodes [1]'s children are in tree.nodes [3] and tree.nodes [4].
tree.nodes [2]'s children are in tree.nodes [5] and tree.nodes [6].
Do you see the pattern? For any node tree.nodes [index], its left child is in tree.nodes [index * 2 + 1] and its right child is in tree.nodes [index * 2 + 2] (provided that these child nodes exist). Notice that the nodes in the array from tree.nodes[tree.numElements/2] to tree.nodes[tree.numElements - 1] are leaf nodes.
Not only can we easily calculate the location of a node's children, but we can also determine the location of its parent node. This task is not an easy one in a binary tree linked together with pointers from parent to child nodes, but it is very simple in our implicit link implementation: tree.nodes [index]'s parent is in tree.nodes[(index- 1)/2].
Because integer division truncates any remainder, (index - 1) / 2 is the correct parent index for either a left or a right child. Thus this implementation of a binary tree is linked in both directions-from parent to child and from child to parent. We take advantage of this fact later in the next chapter.
This tree representation works well for any binary tree that is full or complete. A full binary tree is a binary tree in which all of the leaves are located on the same level and every nonleaf node has two children. The basic shape of a full binary tree is triangular:
Full binary tree A binary tree in which all of the leaves are located on the same level and every nonleaf node has two children
A complete binary tree is a binary tree that is either full or full through the next-to-last level, with the leaves on the last level located as far to the left as possible. The shape of a complete binary tree is either triangular (if the tree is full) or something like the following:
Complete binary tree A binary tree that is either full or full through the next-to-last level, with the leaves on the last level located as far to the left as possible
Figure 8.22 shows some examples of binary trees.
The array-based representation is simple to implement for trees that are full or complete, because the elements occupy contiguous array slots. If a tree is not full or complete, however, we must account for the gaps created by missing nodes. To use the array representation, we must store a dummy value in those positions in the array so as to maintain the proper parent-child relationship. The choice of a dummy value depends on what information is stored in the tree. For instance, if the elements in the tree are nonnegative integers, we can store a negative value in the dummy nodes.
Figure 8.23 illustrates a tree that is not complete as well as its corresponding array. Some of the array slots do not contain actual tree elements, but rather hold dummy values. The algorithms to manipulate the tree must reflect this situation. For example, to determine whether the node in tree.nodes[index] has a left child, you must check whether index * 2 + 1 < tree.numElements, and then check whether the value in tree.nodes [index * 2 + 1] is the dummy value.
We have seen how we can use an array to represent a binary tree. We can also reverse this process, creating a binary tree from the elements in an array. In fact, we can regard any one-dimensional array as representing the nodes in a tree, although the data values that happen to be stored in it may not match this structure in a meaningful way. In Chapter 9, we use this binary tree representation to implement a heap, a new ADT.
< Free Open Study > |
Converted from CHM to HTML with chm2web Pro 2.85 (unicode) |