from here on the program is independent of both the binary tree and the stack implementation
printtree(ptree)
/* Prints the info field values of all
nodes of the binary tree tree.
*/
binarytreepointer *ptree;
{
binarytreepointer null,p,q,rightpointer;
binarytreepointer setnull(),left(),right(),item();
stack s1;
null = setnull();
setstack(&s1);
p = *ptree;
while ((p != null) || !empty(&s1))
if (p != null)
{
printnode(ptree,p);
if (left(p) != null)
{
push(p,&s1);
p = left(p);
}
else
{
push(p,&s1);
p = right(p);
}
}
else
{
do
{
pop(&s1,&q);
if (!empty(&s1))
rightpointer = right(item(&s1));
else
rightpointer = null;
}while(!empty(&s1) &&
(q == rightpointer));
if (q != rightpointer)
p = rightpointer;
}
}
terminalcount(ptree)
/* Prints the number of terminal nodes
in the binary tree tree.
*/
binarytreepointer *ptree;
{
binarytreepointer p,null,setnull(),left(),right();
stack s2;
null = setnull();
setstack(&s2);
p = *ptree;
while ((p != null) || !empty(&s2))
if (p != null)
{
updatetncount(ptree,p,&s2);
push(right(p),&s2);
p = left(p);
}
else
pop(&s2,&p);
}
updatetncount(pt,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 *pt,p;
stack *ps;
{
binarytreepointer null,setnull(),left(),right();
static int tncount;
null = setnull();
if (p == *pt)
tncount = O;
if ((left(p) == null) && (right(p) == null))
{
tncount++;
if (last(ps))
printf("\n The number of terminal nodes\
is %d",tncount);
}
}
replacefirstterminal(ptree,value)
/* Replaces the first terminal node, encountered
in a preorder traversal of binary tree tree, by a
new node with its info field set to the contents
of value.
*/
binarytreepointer *ptree;
int value;
{
binarytreepointer null,p,q,rightpointer;
binarytreepointer setnull(),left(),right(),item();
stack s3;
null = setnull();
setstack(&s3);
p = *ptree;
while ((p != null) | | !empty(&s3))
if (p != null)
{
replacenode(ptree,p,null,&s$,value);
if (left (p) != null)
{
push(p,&s3);
p = left(p);
}
else
{
push(p,&s3);
p = right(p);
}
}
else
{
do
{
pop(&s3,&q);
if (!empty(&s3))
rightpointer = right(item(&s3));
else
rightpointer = null;
}while (!empty(&s3) &&
(q == rightpointer));
if (q != rightpointer)
p = right pointer;
}
}
replacenode(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);
}
}
depth(tree)
/* Returns the depth of the binary tree tree. */
binarytreepointer tree;
{
binarytreepointer setnull(),left(),right();
if (tree == setnull())
return(0);
else
return(1 + max(depth(left(tree)),
depth(right(tree))));
}
max(i,j)
/* Returns the maximum of i and j. */
int i,j;
{
if (i >= j)
return(i);
else
return(j);
}