释放二叉树而不使用递归

指的是这个问题C 中的解除分配二叉树结构 https://stackoverflow.com/questions/32733353/deallocating-binary-tree-structure-in-c?noredirect=1#comment53322817_32733353

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

如果你的节点确实包含有效的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;
  }
}