c - 不用递归释放一个二叉树

Question

引用问题Deallocating binary-tree structure in C

struct Node{
    Node *parent;
    Node *next;
    Node *child;
}

我试图释放一棵二叉树。我遇到的问题是分配的对象是 5520，对自由函数的调用次数是 2747。我不知道为什么，它应该真正释放并遍历树中的所有节点，这是我使用的代码

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++ 
            }
        }
    }

迭代次数为5440，删除次数为2747。

新固定代码:该代码是否正确？

 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);
     }

Answer 1

如果您的节点确实包含有效的 parent 指针，那么整个事情可以以更加紧凑和可读的方式完成

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;
  }
}