Java Reference
In-Depth Information
will use the “)” symbol) to indicate the end of a child list. All leaf nodes are fol-
lowed by a “)” symbol because they have no children. A leaf node that is also the
last child for its parent would indicate this by two or more successive “)” symbols.
Example6.8
For the general tree of Figure 6.3, we get the sequential
representation
RAC)D)E))BF)))
(6.4)
Note that F is followed by three “)” marks, because it is a leaf, the last node
of B's rightmost subtree, and the last node of R's rightmost subtree.
Note that this representation for serializing general trees cannot be used for bi-
nary trees. This is because a binary tree is not merely a restricted form of general
tree with at most two children. Every binary tree node has a left and a right child,
though either or both might be empty. For example, the representation of Exam-
ple 6.8 cannot let us distinguish whether node D in Figure 6.17 is the left or right
child of node B.
6.6
Further Reading
The expression log
n cited in Section 6.2 is closely related to the inverse of Ack-
ermann's function. For more information about Ackermann's function and the cost
of path compression for UNION/FIND, see Robert E. Tarjan's paper “On the effi-
ciency of a good but not linear set merging algorithm” [Tar75]. The article “Data
Structures and Algorithms for Disjoint Set Union Problems” by Galil and Italiano
[GI91] covers many aspects of the equivalence class problem.
Foundations of Multidimensional and Metric Data Structures by Hanan Samet
[Sam06] treats various implementations of tree structures in detail within the con-
text of K-ary trees. Samet covers sequential implementations as well as the linked
and array implementations such as those described in this chapter and Chapter 5.
While these topics are ostensibly concerned with spatial data structures, many of
the concepts treated are relevant to anyone who must implement tree structures.
6.7
Exercises
6.1 Write an algorithm to determine if two general trees are identical. Make the
algorithm as efficient as you can. Analyze your algorithm's running time.
6.2 Write an algorithm to determine if two binary trees are identical when the
ordering of the subtrees for a node is ignored. For example, if a tree has root
node with value R, left child with value A and right child with value B, this
would be considered identical to another tree with root node value R, left
