释放二叉树而不递归

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

Answer 2

这是一棵二叉树！ 由于您选择的名称，人们会感到困惑， next在链接列表中很常见，但类型是重要的，并且您有一个节点正好引用两个相同的节点类型，这一切都很重要。

取自这里： https ： //codegolf.stackexchange.com/a/489/15982您链接到。 我改名为left到child ， right到next 🙂

 void removetree(Node *root) { struct Node * node = root; struct Node * up = NULL; while (node != NULL) { if (node->child != NULL) { struct Node * child = node->child; node->child = up; up = node; node = child; } else if (node->next != NULL) { struct Node * next = node->next; node->child = up; node->next = NULL; up = node; node = next; } else { if (up == NULL) { free(node); node = NULL; } while (up != NULL) { free(node); if (up->next != NULL) { node = up->next; up->next = NULL; break; } else { node = up; up = up->child; } } } } } 

Answer 3

首先要说的是，如果你尝试以非递归的方式解决递归问题，那么你将遇到麻烦。

我看到错误的答案被选为好的答案，所以我会尝试展示我的方法：

我将开始使用指针引用而不是普通指针，因为传递根指针引用可以更容易地检测（和更新）指向根节点的指针。 因此，例程的接口将是：

 void delete_tree(struct node * * const ref); 

它表示对指向根节点的指针的引用。 我将下降到节点，如果child或next为NULL那么只需将引用的指针指向另一个链接就可以自由地消除这个节点（所以我不会丢失它）。 如果节点有两个子节点（ child和next都是!= NULL ）那么我不能删除这个节点，直到其中一个分支折叠，然后我选择其中一个分支并移动引用（我将ref参数const声明为保证我不修改它，所以我使用另一个移动参考为此）

 struct node **moving_reference; 

然后，算法如下：

 void tree_delete(struct node ** const static_ref) { while (*static_ref) { struct node **moving_ref = static_ref; while (*moving_ref) { struct node *to_be_deleted = NULL; if ((*moving_ref)->child && (*moving_ref)->next) { /* we have both children, we cannot delete until * ulterior pass. Just move the reference. */ moving_ref = &(*moving_ref)->child; } else if ((*moving_ref)->child) { /* not both != NULL and child != NULL, * so next == NULL */ to_be_deleted = *moving_ref; *moving_ref = to_be_deleted->child; } else { /* not both != NULL and child == NULL, * so follow next */ to_be_deleted = *moving_ref; *moving_ref = to_be_deleted->next; } /* if, else if */ /* now, delete the unlinked node, if available */ if (to_be_deleted) node_delete(to_be_deleted); } /* while (*moving_ref) */ } /* while (*static_ref) */ } /* delete_tree */ 

我已将此算法包含在一个完整的示例中，向您显示部分树和moving_ref在树中移动时的位置。 它还显示了删除它所需的传递。

 #include  #include  #define N 100 #define D(x) __FILE__":%d:%s: " x, __LINE__, __func__ #define ASSERT(x) do { \ int res; \ printf(D("ASSERT: (" #x ") ==> %s\n"), \ (res = (int)(x)) ? "TRUE" : "FALSE"); \ if (!res) exit(EXIT_FAILURE); \ } while (0) struct node { int key; struct node *child; struct node *next; }; /* struct node */ struct node *node_alloc(void); void node_delete(struct node *n); /* This routine has been written recursively to show the simplicity * of traversing the tree when you can use recursive algorithms. */ void tree_traverse(struct node *n, struct node *p, int lvl) { while(n) { printf(D("%*s[%d]\n"), lvl<<2, p && p == n ? ">" : "", n->key); tree_traverse(n->child, p, lvl+1); n = n->next; } /* while */ } /* tree_traverse */ void tree_delete(struct node ** const static_ref) { int pass; printf(D("BEGIN\n")); for (pass = 1; *static_ref; pass++) { struct node **moving_ref = static_ref; printf(D("Pass #%d: Considering node %d:\n"), pass, (*moving_ref)->key); while (*moving_ref) { struct node *to_be_deleted = NULL; /* print the tree before deciding what to do. */ tree_traverse(*static_ref, *moving_ref, 0); if ((*moving_ref)->child && (*moving_ref)->next) { printf(D("Cannot remove, Node [%d] has both children, " "skip to 'child'\n"), (*moving_ref)->key); /* we have both children, we cannot delete until * ulterior pass. Just move the reference. */ moving_ref = &(*moving_ref)->child; } else if ((*moving_ref)->child) { /* not both != NULL and child != NULL, * so next == NULL */ to_be_deleted = *moving_ref; printf(D("Deleting [%d], link through 'child' pointer\n"), to_be_deleted->key); *moving_ref = to_be_deleted->child; } else { /* not both != NULL and child != NULL, * so follow next */ to_be_deleted = *moving_ref; printf(D("Deleting [%d], link through 'next' pointer\n"), to_be_deleted->key); *moving_ref = to_be_deleted->next; } /* if, else if */ /* now, delete the unlinked node, if available */ if (to_be_deleted) node_delete(to_be_deleted); } /* while (*moving_ref) */ printf(D("Pass #%d end.\n"), pass); } /* for */ printf(D("END.\n")); } /* delete_tree */ struct node heap[N] = {0}; size_t allocated = 0; size_t deleted = 0; /* simple allocation/free routines, normally use malloc(3). */ struct node *node_alloc() { return heap + allocated++; } /* node_alloc */ void node_delete(struct node *n) { if (n->key == -1) { fprintf(stderr, D("doubly freed node %ld\n"), (n - heap)); } n->key = -1; n->child = n->next = NULL; deleted++; } /* node_delete */ /* main simulation program. */ int main() { size_t i; printf(D("Allocating %d nodes...\n"), N); for (i = 0; i < N; i++) { struct node *n; n = node_alloc(); /* the node */ n->key = i; n->next = NULL; n->child = NULL; printf(D("Node %d"), n->key); if (i) { /* when we have more than one node */ /* get a parent for it. */ struct node *p = heap + (rand() % i); printf(", parent %d", p->key); /* insert as a child of the parent */ n->next = p->child; p->child = n; } /* if */ printf("\n"); } /* for */ struct node *root = heap; ASSERT(allocated == N); ASSERT(deleted == 0); printf(D("Complete tree:\n")); tree_traverse(root, NULL, 0); tree_delete(&root); ASSERT(allocated == N); ASSERT(deleted == N); } /* main */ 

Answer 4

为什么不这样做呢？

 void removetree(Node *node) { if (node == NULL) { return; } number_of_iterations++; removetree(node->next); removetree(node->child); free(node); number_of_deletions++; } 

Answer 5

该实现不适用于具有根1的树，该树具有单个子2 。

 NodeOne.parent = null NodeOne.next = null NodeOne.child = NodeTwo NodeTwo.parent = null NodeTwo.next = null NodeTwo.child = null 

执行Removetree(NodeOne)不会在NodeOne上调用remove 。

Answer 6

我会做

 void removeTree(Node *node){ Node *temp; while (node !=NULL){ if (node->child != NULL) { removeTree(node->child); } temp = node; node = node->next; free(temp); } } 

非递归版本：

 void removeTree(Node *node){ Node *temp; while (node !=NULL){ temp = node; while(temp != node) { for(;temp->child == NULL; temp = temp->child); //Go to the leaf if (temp->next == NULL) free(temp); //free the leaf else { // If there is a next move it to the child an repeat temp->child = temp->next; temp->next = temp->next->next; } } node = temp->next; // Move to the next free(temp) } } 

我认为这应该有效

Answer 7

您只释放子树，而不是父节点。 假设child表示节点的left子节点， next表示right子节点。 然后，您的代码变为：

 struct Node{ Node *parent; Node *right; Node *left; } 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->left != NULL) { node = node->left; temp->left = node->right; node->right = temp; } else { node = node->right; remove(temp); number_of_deletions++ } } } 

每次while循环完成一次迭代时，左边的子节点将没有指向它的指针。 以，例如以下树：

  1 2 3 4 5 6 7 

当node是根节点时，会发生以下情况

• node指向’1′
• temp指向’1′
• node现在指向’2′
• temp->left now指向’5′
• node->right现在指向’1′

在下一次迭代中，您将从node指向“2”和temp 。 如您所见，您没有删除节点“1”。 这将重复。

为了解决这个问题，如果要避免递归，可能需要考虑使用BFS和类似队列的结构来删除所有节点。

编辑 BFS方式：

1. 创建队列结构Q
2. 将根节点节点添加到Q
3. 将节点的左节点添加到Q
4. 将节点的右节点添加到Q
5. 自由node并从Q删除它
6. 设置node = Q第一个元素
7. 重复步骤3-6，直到Q变空

这使用了队列是FIFO结构的事实。

Answer 8

@AnT提出的代码不正确，因为它在遍历和释放其左子树之后立即释放节点，但在使用正确的子树执行相同操作之前。 因此，在从右子树升序时，我们将踩到已释放的父节点。

这是一种正确的方法，在C89中。 但它仍然需要parent链接。

 void igena_avl_subtree_free( igena_avl_node_p root ) { igena_avl_node_p next_node; { while (root != NULL) { if (root->left != NULL) { next_node = root->left; root->left = NULL; } else if (root->right != NULL) { next_node = root->right; root->right = NULL; } else { next_node = root->parent; free( root ); } root = next_node; } }} 

直接来自我自己的项目Gena 。