4.10.2 Iterative Copying |

Now we can factor out the recursion, starting with the tail recursion. This process is very similar to what we did with the traversal code, so the details are left for Exercise 1. Let's look at the results part by part:

78. <Iterative copy of BST 78> = /* Copiesorgto a newly created tree, which is returned. */structbst_table*bst_copy_iterative(conststructbst_table*org)

{structbst_node*stack[2 * (BST_MAX_HEIGHT+ 1)];

/* Stack. */intheight= 0; /* Stack height. */

This time, our stack will have two pointers added to it at a time, one
from the original tree and one from the copy. Thus, the stack needs to
be twice as big. In addition, we'll see below that there'll be an extra
item on the stack representing the pointer to the tree's root, so our
stack needs room for an extra pair of items, which is the reason for the
“+ 1” in *stack*[]'s size.

79. <Iterative copy of BST 78> +=structbst_table*new; /* New tree. */conststructbst_node*x; /* Node currently being copied. */structbst_node*y; /* New node being copied fromx. */new=bst_create(org->bst_compare,org->bst_param,org->bst_alloc);new->bst_count=org->bst_count;if(new->bst_count== 0)returnnew;x= (conststructbst_node*) &org->bst_root;y= (structbst_node*) &new->bst_root;

This is the same kind of “dirty trick” already described in Exercise 4.7-1.

80. <Iterative copy of BST 78> +=for(;;)

{while(x->bst_link[0] !=NULL)

{y->bst_link[0]

=org->bst_alloc->libavl_malloc(org->bst_alloc,sizeof*y->bst_link[0]);stack[height++] = (structbst_node*)x;stack[height++] =y;x=x->bst_link[0];y=y->bst_link[0]; }y->bst_link[0] =NULL;

This code moves *x* down and to the left in the tree until it runs out
of nodes, allocating space in the new tree for left children and pushing
nodes from the original tree and the copy onto the stack as it goes.
The cast on *x* suppresses a warning or error due to *x*, a pointer to a
**const** structure, being stored into a non-constant pointer in
*stack*[]. We won't ever try to store into the pointer that we store in
there, so this is legitimate.

We've switched from using *malloc*() to using the allocation function
provided by the user. This is easy now because we have the tree
structure to work with. To do this earlier, we would have had to
somehow pass the tree structure to each recursive call of the copy
function, wasting time and space.

81. <Iterative copy of BST 78> +=for(;;)

{y->bst_data=x->bst_data;if(x->bst_link[1] !=NULL)

{y->bst_link[1] =

org->bst_alloc->libavl_malloc(org->bst_alloc,sizeof*y->bst_link[1]);x=x->bst_link[1];y=y->bst_link[1];break; }else

y->bst_link[1] =NULL;if(height<= 2)returnnew;y=stack[–height];x=stack[–height]; } } }

We do not pop the bottommost pair of items off the stack because these
items contain the fake **struct** **bst_node** pointer that is actually the
address of *bst_root*. When we get down to these items, we're done
copying and can return the new tree.

**See also:**
[Knuth 1997], algorithm 2.3.1C;
[ISO 1990], section 6.5.2.1.

**Exercises:**

**1.** Suggest a step between *bst_copy_recursive_2*() and
*bst_copy_iterative*().
[answer]