1
\$\begingroup\$

I have this function that I hope to be a good alternative to the recursive (thus performance expensive) approach.

#define _free_all(node, yes_no) \
    do { \
        Tree *__i;
        for (__i = node; __i; __i = __i->yes_no); \
        free(; node != __i; __i = __i->parent) { \
            free(__i->value); \
            free(__i); \
        } \
    } while (0)

void Tree_destroy(tree)
    Tree *tree;
{ /* Destroys a Tree object - Non Recursive */
    if (!tree)
        return;
    _free_all(tree, yes);
    _free_all(tree, no);

    if (tree->parent) {
        if (tree->parent->no == info)
            tree->parent->no = NULL;
        else
            tree->parent->yes = NULL;
    }
    free(tree);
}

The two children of each parent are no and yes.

Are there any issues with this approach ?

\$\endgroup\$
11
  • \$\begingroup\$ How are Info and Tree defined? \$\endgroup\$ – Olaf Dietsche Nov 14 '14 at 22:45
  • \$\begingroup\$ @OlafDietsche: Nothing, I just forgot to rename it. I corrected that. \$\endgroup\$ – Amr Ayman Nov 14 '14 at 22:59
  • \$\begingroup\$ Names starting with _ and __ are reserved and best if avoided. \$\endgroup\$ – glampert Nov 15 '14 at 1:30
  • 1
    \$\begingroup\$ Have you actually tested this code? It doesn't free the whole tree. The free_all macro either frees only left nodes or only right nodes, which means that any node in your tree that isn't on the left edge or right edge won't be freed. \$\endgroup\$ – JS1 Nov 15 '14 at 10:50
  • \$\begingroup\$ JS1's comment is exactly the kind of thing I was going to warn about; binary trees and recursion are so intimately tied that any iterative function to do the same work will probably be horrendously complicated, which could lead to missed edge cases, leading to segfaults and memory leaks. \$\endgroup\$ – tsleyson Nov 15 '14 at 19:00
2
\$\begingroup\$

1. Bug

JS1 is quite correct to point out that this does not work: it never visits or frees tree->yes->no (among other nodes).

2. Correct algorithm

Consider a finite state machine with three states:

  1. If tree has a left child, set tree to its left child and go to state 1. Otherwise, go to state 2.

  2. If tree has a right child, set tree to its right child and go to state 1. Otherwise, go to state 3.

  3. (In this state tree has no children.) Destroy tree. If tree had no parent, stop. Otherwise, delete whichever of parent's children is equal to tree, set tree to parent and go to state 1.

This state machine walks the tree in post-order, destroying each node after destroying all of its descendant nodes. Here's one way of translating this into C:

void TreeDestroy(Tree *tree)
{
    for (;;) {
        if (tree->left) {
            tree = tree->left;
        } else if (tree->right) {
            tree = tree->right;
        } else {
            Tree *parent = tree->parent;
            free(tree->value);
            free(tree);
            if (!parent)
                break;
            else if (parent->left == tree)
                parent->left = NULL;
            else if (!parent->left && parent->right == tree)
                parent->right = NULL;
            else
                assert(0); /* can't happen if tree is well-formed */
            tree = parent;
        }
    }
}

(I've used "left" and "right" here because these are the more usual names for the two children of a node in a binary tree.)

3. What if there are no parent pointers?

To iteratively destroy a binary tree with no parent pointers, start with the rotate right operation:

rotate right

void TreeRotateRight(Tree **tree)
{
    Tree *left = (*tree)->left;
    (*tree)->left = left->right;
    left->right = *tree;
    *tree = left;
}

By repeatedly applying the rotate right operation, you can turn a tree into a vine. (A vine is a degenerate tree in which nodes only have right children.)

void TreeToVine(Tree **tree)
{
    while (*tree) {
        while ((*tree)->left)
            TreeRotateRight(tree);
        tree = &((*tree)->right);
    }
}

And then a vine is easy to destroy iteratively:

void TreeDestroy(Tree *tree)
{
    TreeToVine(&tree);
    while (tree) {
        assert(!tree->left);
        Tree *right = tree->right;
        free(tree->value);
        free(tree);
        tree = right;
    }
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.