Now consider the tree of Figure 13.12. It represents the binary tree t of Figure 13.10 during a link-inversion traversal after node.p has been processed. Notice that a path exists in the tree from predp back to the root. Each node has a tag field associated with it, and all tag values are initially zero. Preadp always points to the predecessor of p in t, and every node on the path from predp to the root has its right pointer field pointing to its predecessor if its tag field is 1, and its left pointer field pointing to its predecessor if its tag field is 0. The root of the subtree whose left subtree traversal is complete after the processing of p may be found by following the backward links from predp until a tag value of 0 is encountered. As the path back is followed, a tag of 1 at a predecessor node means we are coming from the node's right subtree. A tag of 0 means we are coming from the left subtree. Again, for node.p this leads to node.p4.
Using the backward links with appropriate tag values to preserve the path to the root is the essential concept of a link-inversion traversal. During the traversal, the creation of appropriate links must be handled. For example, as the path to node.p4 is traversed, after p has been processed, the nodes with tag values of 1 must have their correct right pointer values restored. Then when node.p4 is found (tag = 0), its correct left pointer value must be restored, its tag field set to 1, its right pointer field set to its predecessor, and predp and p correctly updated before node.p4's right subtree is traversed. The traversal is complete when the backtracking leads to a null predp value. Figure 13.13 shows the state of the tree just before node.p4's right subtree is traversed. Node.p must now be processed, then its left pointer field must be set to its predecessor, predp updated to p, and p updated to the left pointer value of node.p. The traversal then continues with the left subtree of p. Initially, p must be set to t and predp to null.
Procedure preorder may be used for the link-inversion traversal if stack is declared to be of type binarytreepointer, and its routines are implemented as follows.
Routine Task
-----------------------------------------------------------------------------
setnull( ) determined by the implementation
setstack(&s) set s to null
push(p,&s) if leftptr.p is not null, then
set leftptr.p to s and s to p
else
set tag(p) to 1, 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 found to false
while((not found) and (s not null))
if tag(s) = 1, then
set pred to s
set tag(s) to 0, s to rightptr.s,
rightptr.pred to p, and p to pred
else
set pred to leftptr.s and leftptr.s to p
if rightptr.s null, then
set found to true, tag(s) to 1, return
rightptr.s, and set rightptr.s to
pred
else
set p to s, set s to pred
if s = null, then
return null.
In this implementation s plays the role of predp.
In a stack traversal, the storage required for the stack is proportional to the depth of the traversed tree. In the threaded-tree and link-inversion traversals, storage is not required for the stack but is required for the tag fields. This storage may actually be available, but unused, because of the implementation of the tree records. In this case, using it for the tag fields costs nothing. Otherwise, the additional storage is proportional to the number of nodes in the traversed tree. For the stack traversal, the constant of proportionality is given by the length of the pointer fields, while in the threaded-tree and link-inversion traversals it is given by the length of the tag fields.
The threaded-tree traversal is simpler than the link-inversion traversal and does not disturb the tree itself during the traversal. This allows more than one program to access the tree concurrently. However, the insertion and deletion of nodes in a threaded tree is more complex and time-consuming. Inorder and postorder traversals may also be done using link inversion.
