4.14.1.2 Displaying BST Structures

The print_tree_structure() function below can be useful for debugging, but it is not used very much by the testing code. It prints out the structure of a tree, with the root first, then its children in parentheses separated by a comma, and their children in inner parentheses, and so on. This format is easy to print but difficult to visualize, so it's a good idea to have a notebook on hand to sketch out the shape of the tree. Alternatively, this output is in the right format to feed directly into the texitree program used to draw the tree diagrams in this book, which can produce output in plain text or PostScript form.

120. <BST print function 120> =
/* Prints the structure of node, 
   which is level levels from the top of the tree. */
static void 
print_tree_structure (const struct bst_node *node, int level) 
{
  /* You can set the maximum level as high as you like.
     Most of the time, you'll want to debug code using small trees,
     so that a large level indicates a “loop”, which is a bug. */
  if (level > 16) 
    {
      printf ("[...]");
      return;
    }

  if (node == NULL)
    return;

  printf ("%d", *(int *) node->bst_data);
  if (node->bst_link[0] != NULL || node->bst_link[1] != NULL) 
    {
      putchar ('(');

      print_tree_structure (node->bst_link[0], level + 1);
      if (node->bst_link[1] != NULL) 
        {
          putchar (',');
          print_tree_structure (node->bst_link[1], level + 1);
        }

      putchar (')');
    }
}

See also 121.

A function print_whole_tree() is also provided as a convenient wrapper for printing an entire BST's structure.

121. <BST print function 120> +=
/* Prints the entire structure of tree with the given title. */
void 
print_whole_tree (const struct bst_table *tree, const char *title) 
{
  printf ("%s: ", title);
  print_tree_structure (tree->bst_root, 0);
  putchar ('\n');
}