This implementation will not be pursued further but is similar in character to the sequential implementation for binary trees. This means that formulas can be derived to compute the array position of a node's predecessor and successors, which are important requirements for tree processing. Also, this representation is convenient for essentially static, healthy-looking (nonparse) trees.
Another representation is based on a natural generalization of the linked representation for binary trees. Simply expand each record so that it has as many pointer fields as it has subtrees. However, this leads to variable-length records, which are usually not desirable. The variable-length records occur because nodes need not all have the same number of successors. Further, it may not even be possible to predict in advance what the greatest number of successors will be.When it is known that the tree will be a k-ary tree, then all records could be made the same length, large enough to accommodate k subtree pointers. This gives a fixed record size but can result in considerable wasted storage for unused pointer fields within records. This is particularly true for sparse trees.
Surprisingly, there is a way to represent a tree as a binary tree, which then allows all records to be of fixed length. This is an important result. Since any tree can be represented by a binary tree, studying only binary trees is really no restriction at all.
Example 7.4
Let us now look at how to represent a specific tree as a binary tree. Consider the tree of Figure 7.13(a). How can this tree be represented as a binary tree? n
The binary tree is obtained as follows: First, create a root A of the binary tree to correspond to the root A of the tree. Next, pick any successor of A in the tree?/FONT>say, B?/FONT>and create a node B in the binary tree as A's left successor. Then take the remaining siblings of B, which are C and D in this case, and let C be B's right successor and D be C's right successor, in the binary tree. So far this yields the binary tree shown in Figure 7.13(b). If we view this procedure as the processing of node A of the tree, then the binary tree is completed by repeating this procedure for every other node of the tree. For example, after node B is processed (that is, its successors have been added to the binary tree), the result is Figure 7.13(c). The final binary tree created using this procedure appears in Figure 7.13(d).
Applying this procedure, given any tree, a corresponding binary tree can be constructed. The specific binary tree generated will depend on the order in which successors are taken in the tree. For instance, had C been selected initially as the first successor of A, then the resultant binary tree would be different. If the ordering of each node's successors is specified and they are taken in the specified order, then the construction creates a unique binary tree for each tree. In any case, a tree with n nodes will correspond to a binary tree with n nodes. It is not difficult to find an algorithm that, given a binary tree with no right subtree, can reverse the construction and generate the tree it represents. This means that when the tree is ordered, there is a unique binary tree that can be constructed to represent it. Conversely, given a binary tree with no right subtree, there is a unique tree that it represents, which can also be constructed. Hence there are exactly as many trees with n nodes as there are binary trees with n nodes and no right subtrees.
(a) Initial Tree
(b) Binary Tree for Nodes A - D
(c) Binary Tree for Nodes A - G
(d) Final Binary Tree
Figure 7.13 Representation of a General Tree as a Binary Tree