7.10 Destruction

Destroying a threaded binary tree is easy. We can simply traverse the tree in inorder in the usual way. We always have a way to get to the next node without having to go back up to any of the nodes we've already destroyed. (We do, however, have to make sure to go find the next node before destroying the current one, in order to avoid reading data from freed memory.) Here's all it takes:

283. <TBST destruction function 283> =
void 
tbst_destroy (struct tbst_table *tree, tbst_item_func *destroy) 
{
  struct tbst_node *p; /* Current node. */
  struct tbst_node *n; /* Next node. */

  p = tree->tbst_root;
  if (p != NULL)
    while (p->tbst_tag[0] == TBST_CHILD)
      p = p->tbst_link[0];

  while (p != NULL) 
    {
      n = p->tbst_link[1];
      if (p->tbst_tag[1] == TBST_CHILD)
        while (n->tbst_tag[0] == TBST_CHILD)
          n = n->tbst_link[0];

      if (destroy != NULL && p->tbst_data != NULL) 
        destroy (p->tbst_data, tree->tbst_param);
      tree->tbst_alloc->libavl_free (tree->tbst_alloc, p);

      p = n;
    }

  tree->tbst_alloc->libavl_free (tree->tbst_alloc, tree);
}

This code is included in 253, 302, and 338.