www.delorie.com/gnu/docs/avl/libavl_63.html   search  
Buy GNU books!

GNU libavl 2.0.1

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

5.10.1 Recursive Copying

The "obvious" way to copy a binary tree is recursive. Here's a basic recursive copy, hard-wired to allocate memory with malloc() for simplicity:

/* Makes and returns a new copy of tree rooted at x. */
static struct bst_node *
bst_copy_recursive_1 (struct bst_node *x)
{ struct bst_node *y; if (x == NULL) return NULL; y = malloc (sizeof *y); if (y == NULL) return NULL; y-&#62;bst_data = x-&#62;bst_data; y-&#62;bst_link[0] = bst_copy_recursive_1 (x-&#62;bst_link[0]); y-&#62;bst_link[1] = bst_copy_recursive_1 (x-&#62;bst_link[1]); return y; }

But, again, it would be nice to rewrite this iteratively, both because the iterative version is likely to be faster and for the sheer mental exercise of it. Recall, from our earlier discussion of inorder traversal, that tail recursion (recursion where a function calls itself as its last action) is easier to convert to iteration than other types. Unfortunately, neither of the recursive calls above are tail-recursive.

Fortunately, we can rewrite it so that it is, if we change the way we allocate data:

/* Copies tree rooted at x to y, which latter is allocated but not 
yet initialized. */ static void
bst_copy_recursive_2 (struct bst_node *x, struct bst_node *y)
{ y-&#62;bst_data = x-&#62;bst_data; if (x-&#62;bst_link[0] != NULL)
{ y-&#62;bst_link[0] = malloc (sizeof *y-&#62;bst_link[0]); bst_copy_recursive_2 (x-&#62;bst_link[0], y-&#62;bst_link[0]); } else
y-&#62;bst_link[0] = NULL; if (x-&#62;bst_link[1] != NULL)
{ y-&#62;bst_link[1] = malloc (sizeof *y-&#62;bst_link[1]); bst_copy_recursive_2 (x-&#62;bst_link[1], y-&#62;bst_link[1]); } else
y-&#62;bst_link[1] = NULL; }


1. When malloc() returns a null pointer, bst_copy_recursive_1() fails "silently", that is, without notifying its caller about the error, and the output is a partial copy of the original tree. Without removing the recursion, implement two different ways to propagate such errors upward to the function's caller:

  1. Change the function's prototype to:


  2. Without changing the function's prototype. (Hint: use a statically declared struct bst_node).

In each case make sure that any allocated memory is safely freed if an allocation error occurs. [answer]

2. bst_copy_recursive_2() is even worse than bst_copy_recursive_1() at handling allocation failure. It actually invokes undefined behavior when an allocation fails. Fix this, changing it to return an int, with nonzero return values indicating success. Be careful not to leak memory. [answer]

[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

  webmaster     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003