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;

}

}