It is remarkable that an algorithm has been found which does not require a stack or even tag fields. This is the Robson traversal, the final stackless traversal we consider. Again, we give a preorder version, although it may be used for inorder and postorder traversals as well.
Consider the tree of Figure 13.14. In the link-inversion traversal, for every descent to the left from node.p (that is, every traversal of the left subtree of node.p), the left pointer field of node.p was set to point to node.p's predecessor. For every descent to the right (to traverse the right subtree of node.p), the leftpointer of node.p was restored to its original value, the tag of node.p was set to 1, and the right pointer field of node.p was set to point to node.p's predecessor. Consequently, having completed the traversal of the left subtree of some node q, it was possible to follow the backward pointing pointers to get to q. Q was the first node encountered with a tag value of 0, on the path back.
The Robson traversal does not have tag fields available for this purpose. Instead, a stack is kept in the tree itself, which will allow node q to be found. Q is the root of the most recent subtree, whose nonnull left subtree has already been traversed and whose nonnull right subtree is in the process of being traversed. A variable top is used, and kept updated, to point to the current node q. A variable stack is used, and kept updated, to point to the next most recent subtree whose nonnull left subtree has already been traversed and whose nonnull right subtree is in the process of being traversed. Variables p and predp are used, as in link inversion, to point to the node currently being processed and to its predecessor, respectively. Each stack entry, except the current top entry, is kept in the "rightmost" terminal node of one of the subtrees whose nonnull left subtree has been completely traversed, and whose nonnull right subtree is in the process of being traversed. In Figure 13.14, when node.p is being processed, there are four subtrees whose left subtrees have already been traversed and whose right subtrees are currently being traversed. Their roots are labeled 1 to 4 in Figure 13.14. Nodes 1, 3, and 4 have nonnull left subtrees. Each of these nodes has its left pointer field pointing to its predecessor and its right pointer pointing to the root of its left subtree. Node 2, which has a null left subtree, has its original null value, and its right pointer field is pointing to its predecessor. Nodes 1, 3, and 4 are thus the roots that must have stack entries. Top points to the most recent, node 1. Stack points to the stack entry corresponding to the next most recent root, node 3. This stack entry is kept in the rightmost terminal node of node 1's left subtree. This rightmost node has its left pointer field pointing to the node that contains the next stack entry, and its right pointer field pointing to its corresponding root (node 3 in this case). All stack entries (except the first, pointed to by top) have this same format. In Figure 13.14, the last stack entry points to node 4.
Notice that a path back to the root always exists from node.predp. In Figure 13.14, after node.p is processed, the traversal of node 1's right subtree has been completed. This also completes the traversal of the right subtrees of nodes 2 and 3 and the left subtree of node 3's predecessor. The Robson traversal now proceeds by following the backward path, restoring appropriate left or right subtrees along the way, until the predecessor of node 3 is encountered. At this point, its right subtree must be traversed. Figure 13.15 shows the situation just before that traversal . During the traversal of the backward path, if node.predp has a null right subtree, or top=predp, then we are coming from the left subtree of node.predp, otherwise from the right subtree. Thus the stack entries allow node q to be found even though no tag fields are used.
During the backtracking, the stack is popped, and top is updated as necesssary. Top and stack are initialized to null, predp to null, and p to t. An additional variable avail is used and updated to point to a terminal node every time one is encountered, so that its pointer fields are available if a new stack entry must be created. In this case, the available node must retain a pointer to node.top in its right pointer field and a pointer to the current entry to which stack points in its left pointer field; stack must be updated to point to the new entry; and top must be updated to point to the new top root. At all times, the path from predp back to the root is stored in the tree, as well as the stack of entries pointing to roots of subtrees (with nonnull left subtrees), whose left subtree traversals have completed, and whose right subtrees are being traversed. Each node along the path from predp to the root is in one of the following states:
If the node's left subtree is being traversed, then
its left pointer is pointing to its predecessor, and its right pointer is undisturbed.
If the node's right subtree is being traversed, then
if the node has a null left subtree, then
its right pointer is pointing to its predecessor
else
its left pointer is pointing to its predecessor, and its right pointer is pointing to
the root of the node's left subtree.
The following routines are to be used with the preorder traversal so that it implements the Robson traversal. Stack is declared to be of the same type as binarytreepointer, and s plays the role of predp.
Figure 13.14 Robson Traversal Configuration of the Binary Tree T
Figure 13.15 Robson Traversal before P Is Processed in the Binary Tree T
Routine Task
-----------------------------------------------------------------------------
setnull( ) determined by the implementation
setstack(&s) sets top, stack, and s to null
push(p,&s) if leftptr.p is not null then
set leftptr.p to s and s to p
else
set rightptr.p to s and s to p
left(p) returns a copy of leftptr.p
right(p) returns a copy of rightptr.p
nextsubtree(&s, &p) set avail to p
set found to false
while((not found) and (s not null))
if top = s, then
save stack in hold, pop the stack by setting
top to rightptr.stack, stack to leftptr.
stack, and leftptr.hold and
rightptr.hold to null. Save leftptr.s in
pred, restore leftptr.s by setting it to
rightptr.s, restore rightptr.s by setting it
to p, set p to s, and s to pred
else
if leftptr.s = null, then
save rightptr.s in pred, restore
rightptr.s by setting it to p, set p to s,
and s to pred
else
if rightptr.s null, then
push an entry for s onto the stack by
setting leftptr.avail to stack,
rightptr.avail to top, stack to
avail, and top to s. Return the value
of rightptr.s, set rightptr.s to p,
and set found to true
else
save leftptr.s in pred, restore
leftptr.s by setting it to p, set p to s,
and s to pred.
if s = null, then
return null.