These algorithms may be written assuming a particular binary tree implementation, such as arrays or pointer variables. Instead, to emphasize data abstraction and functional modularity, the following function, which is independent of the tree implementation, has been chosen. The function is a preorder traversal saving the path from the root on the stack.
For each traversal, the basic concept is described. Then the appropriate implementation for the routines of the procedure is described.
Consider the binary tree of Figure 13.10, and suppose node.p has just been processed during the traversal using the preorder procedure. The stack will contain pointers p1, p2, p3, p4, p5, p6, and p7. At this point, the traversal of the left subtree of node.p4 has been completed. The purpose of the nextsubtree(&s,&p) function in the preorder traversal algorithms is to find node.p4, to allow the traversal to pick up at its right subtree. In general, whenever the stack is not empty, a null p value signifies the completion of the traversal of the left subtree of some node. The traversal must then pick up at that node's right subtree. There may be more than one such node; it is the most recent that must be found. The stack allows this node, and its right subtree, to be found conveniently. Nextsubtree(&s,&p) is called after the terminal node pointed to by p has been processed. It finds the nonnull right subtree that must be traversed next, returns a pointer to it, and updates the stack to reflect the path from that subtree's root to the root of the tree. If no such nonnull right subtree exists, then it returns a null value. Each of the tree traversals we now consider actually uses stack information, but it is, in effect, stored in the tree, eliminating the requirement for additional stack storage. The preorder procedure treats the tree as a data abstraction, so it is independent of the tree implementation.
preorder(pt)
/* Preorder traverses the binary tree. */
binarytreepointer *pt;
{binarytreepointer null,p,lptr,rptr;
binarytreepointer setnull(),left(),right(),nextsubtree();
stack s;
null = setnull();
p = *pt;
setstack(&s);
while(p != null)
{process(pt,p);
lptr = left(p);
if(lptr != null)
{push(p,&s);
p = lptr;
}
else
{rptr = right(p);
if(rptr != null)
{push(p,&s);
p = rptr;
}
else
p = nextsubtree(&s,&p);
}
}
}
Figure 13.10 A Binary Tree T