refering to the question Deallocating binary-tree structure in C
struct Node{
Node *parent;
Node *next;
Node *child;
}
I tried to free a binary tree. The problem I have is the allocated objects are 5520 and the number of calls to the free functions is 2747. I don't know why, it should really free and iterate all over the nodes in the tree, here is the code that I use
int number_of_iterations =0;
int number_of_deletions =0;
void removetree(Node *node)
{
number_of_iterations++;
while(node != NULL)
{
Node *temp = node;
if(node->child != NULL)
{
node = node->child;
temp->child = node->next;
node->next = temp;
}
else
{
node = node->next;
remove(temp);
number_of_deletions++
}
}
}
Number of iteration is 5440 and the number of deletions is 2747.
New Fixed code: is that code correct ?
const Node *next(const Node *node)
{
if (node == NULL) return NULL;
if (node->child) return node->child;
while (node && node->next == NULL) {
node = node->parent;
}
if (node) return node->next;
return NULL;
}
for ( p= ctx->obj_root; p; p = next(p)) {
free(p);
}
If your nodes do indeed contain valid parent
pointers, then the whole thing can be done in a much more compact and readable fashion
void removetree(Node *node)
{
while (node != NULL)
{
Node *next = node->child;
/* If child subtree exists, we have to delete that child subtree
first. Once the child subtree is gone, we'll be able to delete
this node. At this moment, if child subtree exists, don't delete
anything yet - just descend into the child subtree */
node->child = NULL;
/* Setting child pointer to null at this early stage ensures that
when we emerge from child subtree back to this node again, we will
be aware of the fact that child subtree is gone */
if (next == NULL)
{ /* Child subtree does not exist - delete the current node,
and proceed to sibling node. If no sibling, the current
subtree is fully deleted - ascend to parent */
next = node->next != NULL ? node->next : node->parent;
remove(node); // or `free(node)`
}
node = next;
}
}