from here on the program is independent of the binary tree implementation
main()
/* Reads the data for nodes of a binary tree, creates
the tree and prints how many terminal nodes it
has and its depth, reads the value for the new node,
replaces the first terminal node in preorder access
by the new node, and then prints all the final
binary tree's nodes, its terminal count, and its
depth.
*/
{
int n,value;
binarytreepointer t,setnull(),avail();
printf("\n enter binarytree 0 for null tree 1\
otherwise \n");
scanf("%d",&n);
if (n == 0)
t = setnull();
else
{
t = avail();
createtree(&t);
}
printtree(&t);
terminalcount(&t);
printf("\n The depth is %d",depth(t));
printf("\n enter value ");
scanf("%d",&value);
replacefirstterminal(&t,value);
printtree(&t);
terminalcount(&t);
printf("\n The depth is %d",depth(t));
}
createtree(ptree)
/* Read the data and create the binary tree tree. */
binarytreepointer *ptree;
{
binarytreepointer l,r,setnull(),left(),right();
if (*ptree != setnull())
{
createnode(ptree);
l = left(*ptree);
createtree(&l);
r = right(*ptree);
createtree(&r);
}
}
createnode(pptr)
/* Reads the data, and fills in the fields
of the node pointed to by ptr.
*/
binarytreepointer *pptr;
{
int leftlink,rightlink,value;
binarytreepointer setnull(),avail();
printf("\n enter info \n");
scanf("%d",&value);
setinfo(*pptr,&value);
printf("\n enter enter left & right ptrs \n");
scanf("%d %d",&leftlink,&rightlink);
if (leftlink == 0)
setleft(*pptr,setnull());
else
setleft(*pptr,avail());
if (rightlink == 0)
setright(*pptr,setnull();
else
setright(*pptr,avail());
}
#define LIMIT 50
typedef binarytreepointer whatever;
typedef struct
{
whatever stackarray[LIMIT];
int top;
}stack;
#define TRUE 1
#define FALSE 0
setstack(ps)
/* Sets the stack s to empty. */
stack *ps;
{
(*ps).top = -1;
}
empty(ps)
/* Returns true only if stack s is empty.*/
stack *ps;
{
return((*ps).top == -1);
}
push(value,ps)
/* Inserts value at the top of stack s. */
whatever value;
stack *ps;
{
if ((*ps).top == (LIMIT - 1))
overflow(ps);
else
{
(*ps).top = (*ps).top + 1;
(*ps).stackarray[(*ps).top] = value;
}
}
pop(ps,pvalue)
/* Removes the top entry of stack s
and copies its contents into value.
*/
stack *ps;
whatever *pvalue;
{
if (empty(ps))
underflow(ps);
else
{
*pvalue = (*ps).stackarray[(*ps).top];
(*ps).top = (*ps).top - 1;
}
}
whatever item(ps)
/* Returns a copy of the top entry on stack s. */
stack *ps;
{
return((*ps).stackarray[(*ps).top]);
}
last(ps)
/* Returns true only if stack s
contains no non null pointers.
*/
stack *ps;
{
int i,temp;
binarytreepointer null,setnull();
null = setnull();
temp = TRUE;
for (i=0;i<=(*ps).top;i++)
if ((*ps).stackarray[i] != null)
temp = FALSE;
return(temp);
}
overflow(ps)
/* Prints a message if the stack overflows. */
stack *ps;
{
printf("\n stack overflow ");
}
underflow(ps)
/* Prints a message if the stack underflows. */
stack *ps;
{
printf("\n stack underflow ");
}
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);