A threaded tree implementation of the preorder traversal procedure is shown in Figure 13.11. It resulted from the replacement of the null left and right pointer field values of each node t by a pointer to the predecessor and to the successor, respectively, of that node in an inorder traversal of t. These pointers are called threads. The "leftmost" node of t does not have a predecessor, and the "rightmost" node of t does not have a successor. Their left and right null pointers, respectively, are left unchanged and are not considered threads. We assume that a field is associated with each node to indicate whether the node contains threads in its left link field, in its right link field, in both, or in neither.
To preorder traverse threaded trees, proceed as before, but whenever a node with threads is reached, follow its right pointer. This pointer leads directly to the node whose right subtree must then be preorder traversed. Notice, for example, that the right thread of node.p points to node.p4. The traversal is complete when a null right thread is encountered. Threaded trees may also be easily inorder and postorder traversed.
Procedure preorder may be used for the traversal of a threaded tree, with stack declared to be of type binarytreepointer, by implementing its routines as follows:
Routine Task
--------------------------------------------------------------------
setnull( ) determined by the implementation (array or pointer
variables)
setstack(&s) sets s to null
push(p,&s) sets s to p
left(p) returns a copy of leftptr.p if it is not a thread, and a
null value otherwise
right(p) similar to left(p)
nextsubtree(&s,&p) set s to p
while (rightptr.s is a thread),
set s to rightptr.s
return a copy of rightptr.s