Example 7.5
Let the task for this example be the development of an algorithm to generate the binary tree corresponding to a general tree. n
In order to do this we must be able to traverse a general tree. As it is traversed, we can generate the binary tree by properly processing each node as it is accessed. A nonrecursive algorithm to preorder traverse a tree t follows.
Nonrecursive Tree Preorder Traversal
1. Set p to t
2. Setstack_t(ts)
3. While p is not null or not empty_t(ts),
if p is not null, then
process(t,p)
For each successor pointer ps of node.p,
except next(p),
push_t(ps,ts)
Update p to next(p)
else
pop_t(ts,p)
This algorithm is a generalization of the nonrecursive preorder traversal of a binary tree that saves right pointers. In the binary tree case, the next subtree is the left subtree, and only one successor of the node just processed must be saved?/FONT>the right successor. The difference is that now all the subtree pointers of the node just processed, except for the next one, must be saved.
Now that we have a general tree traversal, it will be adapted to our task. Let bt point to the binary tree to be generated by the algorithm. Recall the list-structure representation of a binary tree. Think of the leftpointer field of each node of bt as pointing to a sublist. This sublist contains all the successors of the corresponding node in t. Thus, in Figure 7.13(d), node A of the binary tree representation has a leftpointer field pointing to the sublist consisting of nodes B, C, and D. These are the successors of A in the general tree, Figure 7.13(a). Similarly, D has a leftpointer field pointing to the sublist consisting of I and J, the successors of D in the general tree.
Consequently, to produce bt, when a node of t is processed we must
Create a sublist consisting of all its successors
Set the leftpointer field of the corresponding node in bt to point to this sublist
Copy the info field of the node in t into the info field of the corresponding node in bt
The rightpointer fields of these nodes in bt serve as the link fields of the sublist.
Recall that, as we preorder traverse a general tree t, we are preorder traversing its corresponding binary tree, bt. That is, the order in which the nodes of t are accessed is exactly the same as the order in which the corresponding nodes of bt are accessed. Thus we can achieve a solution by preorder traversing both t and bt at the same time, and processing the corresponding nodes as described above. For example, if this were carried out on the general and final binary tree of Figure 7.13, and nodes A, B, E, F, G, and C had been processed, we would have generated the binary tree shown as Figure 7.14(b).
Suppose p points to the node currently being processed in t. Let pb point to the corresponding node in bt. In the example, p would now point to D of t and pb to D of bt.
After processing the node to which p points, we can update p to point to one of its successors, next(p), and stack on ts all pointers to the remaining successors. These pointers represent the latest postponed obligations for the preorder traversal of t. Next (p) is a function returning a pointer to the successor of p that is not stacked, or a null pointer if there are no successors. At the same time, to keep track of the postponed obligations for bt's preorder traversal, we will keep a parallel stack, bts. Only nonnull pointers will be pushed onto bts. When the top pointer in stack ts is popped, the top pointer in bts will also be popped. These pointers will then point to corresponding nodes?/FONT>one in t, the other in bt. Storage can be created for the nodes of bt as the traversal proceeds by using avail to return a pointer to the available storage for a node, since a pointer variable implementation is used for the binary tree.
One last detail remains. In order to do the processing required on node.p and node.pb, process will be invoked. As already noted, process must create a sublist consisting of new nodes corresponding to the successors of node.p in t, set leftptr.pb to point to that sublist, and copy info.p into info.pb. We assume that a procedure create, given p, creates the required sublist, and returns with first pointing to the first node of that sublist. The preorder traversal algorithm to create the binary tree corresponding to a general tree is as follows:
Nonrecursive Algorithm to Generate a Binary Tree Corresponding to a General Tree
1. Set p to t
If p is null
Set bt to null
else
bt = avail()
Set pb to bt
2. Setstack_t(ts)
Setstack_bt(bts)
3. While p is not null or not empty_t(ts),
if p is not null, then
process(t,bt,p,pb).
For each successor pointer ps of node.p, except next(p),
push_t(ps,ts)
If right(pb) is not null
push_bt(right(pb),bts)
p = next(p)
pb = left(pb)
else
pop_t(ts,p)
pop_bt(bts,pb).
The process algorithm to be used in the preorder traversal is:
Create(p,first)
Set leftptr.pb to first
Set info.pb to info.p
Notice that the traversal of the binary tree bt is embedded in the traversal of the general tree t. Also, suffixes have been used to distinguish the stack storing pointers to nodes of the general tree from the stack storing pointers to nodes of the binary tree. Finally, since the tree t is not ordered, the function next is free to pick any successor. The order in which the rest of the successors are placed on the stack is arbitrary but must determine the order in which create places them on the sublist. You should simulate this algorithm on the tree of Figure 7.13(a) to see how it works.
The correspondence between an ordered tree and its binary tree can now be defined more formally. In this case the binary tree corresponding to a tree is unique. An ordered tree t may be represented by a binary tree bt as follows:
Each node of t corresponds to a node of bt,
If node n of t corresponds to node nb of bt, then the leftmost successor of n in t corresponds to the left successor of nb in bt;
All other siblings of n in t form a right chain from the node in bt corresponding to the leftmost successor of n in t.
We may now give a recursive definition specifying an algorithm for generating the binary tree bt representing the general ordered tree t.
To generate a binary tree corresponding to an ordered tree:
If t is null
Set bt to null
else
Create the root node of bt corresponding to the root of t.
If t has a subtree, then generate the binary tree bt.left corresponding to the leftmost subtree of t,t.leftmost, and make the generated binary tree the left subtree of bt.
For every other subtree of t, in order, generate the binary tree corresponding to the subtree, and insert it at the end of the right chain of bt.left.
For illustration this algorithm is applied to the ordered tree in t in Figure 7.15(a).
First create the root of BT corresponding to the root of t shown in Figure 7.15(b). To carry out statement 2, note that t has three subtrees with B at the root of its leftmost subtree. We must thus generate bt.left to orrespond to Figure 7.15(c). To do this, apply the definition to this tree and obtain Figure 7.15(d) as its corresponding binary tree. Completing the first part of statement 2 for t yields the binary tree shown in Figure 7.15(e).
To complete the second part of statement 2, generate the binary tree for the next subtree of t, with C at its root, and then insert it at the end of the right chain of B to obtain Figure 7.15(f). Finally, do the same for the last subtree of A, with D at its root, and complete the application to t, to obtain the result shown in Figure 7.15(g).
This is another example for which we found a recursive solution. Compare the clarity and conciseness of the recursive solution with that of the nonrecursive solution.
Figure 7.14 Binary Tree BT Generated from General Tree T
Figure 7.15 Generation of Binary Tree BT from an Ordered Tree T