In this section a number of examples are presented to show how the traverse functions developed thus far can be applied to develop solutions to programming problems.
Example 7.1
Print the number of terminal nodes in a binary tree tree. n
The nonrecursive preorder traversal that saves right subtree pointers on a stack will be used to perform this task. The other versions could have been adapted as readily. The approach taken is to leave the traverse function as it is and write process to turn preorder into a solution to the problem.
To accomplish this, process must test each node it deals with to see if it is a terminal node. If so a counter, tncount, should be increased by 1. Making tncount a static variable in process allows its values to be preserved between calls to process. The first time process is called during the traversal it must initialize tncount to zero, and the last time it is called, in addition to updating tncount, process must print its final value.
If p points to the current record to be processed, then when p points to the root of the traversed tree tree, process has been called for the first time, so it must set tncount to zero. But how can process recognize when p points to the last node so that tncount can be printed? To do this, process must have access to the stack s. When s contains no nonnull pointers and node.p is a terminal node, then node.p is the last node. Assume that a function last returns true if s contains no nonnull pointers and false otherwise. Consequently s must be a parameter of, or global to, process. Finally, we must assume that only nonnull binary trees are to be considered since process is invoked by preorder only when tree is not null. Process may now be defined as follows.
It would certainly be more efficient to make null global so that setnull would not be invoked for each node. Similarly, setting tncount to zero in preorder could remove the need for the (p == *ptree) test for each node. In fact, it would be easier to take a second approach to finding a solution. Namely, modify preorder so that it sets tncount to zero initially, and after its while loop is exited, simply print tncount. This second solution is considerably more efficient, because the test performed by last is not needed. The second approach is more efficient, but it involves changing a traversal, which may be already compiled. Which approach to use depends on what alternatives are available and just how important the extra efficiency is.
Example 7.2
The second example concerns the problem of inserting a new node in the binary tree tree in place of the first terminal node encountered in a preorder traversal of tree. The information field value of the new node is to be copied from that of the record value. n
In this case process will be written to make a solution out of the nonrecursive version of preorder that stores the path from the root to the node being processed. This is convenient, since the predecessor of the node to be processed is required by process when the insertion is made, and it will be the top stack entry at that time.
When process is called, it tests whether the node is a terminal node. Since it will cause the traversal to be terminated after the replacement, this must be the first terminal node. Storage is then obtained for the new record and its fields filled in properly. Since it will be a terminal node, its pointer fields are set to null. To insert the new record, the predecessor of the terminal node must have one of its pointer fields set to point to the new record. The correct one is determined by whether the replaced record was its left or right successor. The special case of the insertion occurring at the root requires only that tree be set to point to the new record. Finally, setting the stack to empty ensures that the traversal will be aborted.
Value is passed by preorder to process. Item simply returns a copy of the top stack entry.
Example 7.3process(ptree,p,ps)
/* Prints the number of terminal nodes in
binary tree tree when p points to the last
node in a preorder traverse of tree which
saves right pointers on stack s.
*/
binarytreepointer *ptree,p;
stack *ps;
{binarytreepointer null,setnull(),left(),right();
static int tncount;
null = setnull();
if(p == *ptree)
tncount = 0;
if((left(p) == null) && (right(p) == null))
{tncount++;
if(last (ps))
printf("\n The number of terminal nodes is %d",tncount);}
}
process(ptree,p,null,ps,value)
/* If p points to the first terminal node, encountered
in a preorder traversal of binary tree tree that saves
the path to the root on stack s, then replaces that node by
a new node whose info field is set to the contents of value.
*/
binarytreepointer *ptree,p,null;
stack *ps;
int value;
{binarytreepointer q,ptr,avail(),
left(),right();
if((left(p) == null)&&(right(p) == null)
{ptr = avail();
setinfo(ptr,&value);
setleft(ptr,null);
setright(ptr,null);
if(p != *ptree)
{q = item(ps);
if(left(q) == p)
setleft(q,ptr);
else
setright(q,ptr);
}
else
*ptree = ptr;
setstack(ps);
}
}