Let T be a binary tree with n positions that is realized with an array representation A, and let f() be the level numbering function of the positions of T, as given in Section 8.3.2. (pictures) Give pseudocode descriptions of each of the methods root, parent, left, right, isExternal, and isRoot. This is for data structure in java.
8.3. Implementing Trees 331 8.3.2 Array-Based Representation of a Binary Tree An alternative representation of a binary tree T is based on a way of numbering the positions of T. For every position p of T, let f(p) be the integer defined as follows. If p is the root of T, then f(p) =0. If p is the left child of position q, then f(p) = 2f(q) +1. If p is the right child of position q, then f(p) = 2f(q) +2. The numbering function f is known as a level numbering of the positions in a binary tree T, for it numbers the positions on each level of T in increasing order from left to right. (See Figure 8.10.) Note well that the level numbering is based on potential positions within a tree, not the actual shape of a specific tree, so they are not necessarily consecutive. For example, in Figure 8.10(b), there are no nodes with level numbering 13 or 14, because the node with level numbering 6 has no children. (a) 6 10 11 12 13 14 (b) 10 3 Figure 8.10: Binary tree level numbering: (a) general scheme; (b) an example. 332 Chapter 8. Trees The level numbering function f suggests a representation of a binary tree T by means of an array-based structure A, with the element at position p of T stored at index f(p) of the array. We show an example of an array-based representation of a binary tree in Figure 8.11. 4 6 4 2 11 3 9 5 + +4 2. 31 95 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Figure 8.11: Representation of a binary tree by means of an array. One advantage of an array-based representation of a binary tree is that a posi- tion p can be represented by the single integer f(p), and that position-based meth- ods such as root, parent, left, and right can be implemented using simple arithmetic operations on the number f(p). Based on our formula for the level numbering, the left child of p has index 2f(p) +1, the right child of p has index 2f(p) +2, and the parent of p has index Lf(p) - 1)/2]. We leave the details of a complete array- based implementation as Exercise R-8.16. The space usage of an array-based representation depends greatly on the shape of the tree. Let n be the number of nodes of T, and let fm be the maximum value of f(p) over all the nodes of T. The array A requires length N = 1+ fm, since elements range from A[0] to A[fm]. Note that A may have a number of empty cells that do not refer to existing positions of T. In fact, in the worst case, N = 2" 1, the justification of which is left as an exercise (R-8.14). In Section 9.3, we will see a class of binary trees, called "heaps for which N = n. Thus, in spite of the worst-case space usage, there are applications for which the array representation of a binary tree is space efficient. Still, for general binary trees, the exponential worst-case space requirement of this representation is prohibitive. Another drawback of an array representation is that many update operations for trees cannot be efficiently supported. For example, removing a node and promoting its child takes O(n) time because it is not just the child that moves locations within the array, but all descendants of that child
