如何删除C中二叉树中的元素？

我想了解二叉树中节点的删除。这是我从教程中找到的解释相同的代码片段。如何删除C中二叉树中的元素？

节点如下：

struct node 
{ 
    int key_value; 
    struct node *left; 
    struct node *right; 
};

来源：http://www.cprogramming.com/tutorial/c/lesson18.html

void destroy_tree(struct node *leaf) 
    { 
     if(leaf != 0) 
     { 
      destroy_tree(leaf->left); 
      destroy_tree(leaf->right); 
      free(leaf); 
     } 
    }

我的疑问是关于free(leaf)部分。我的意思是，作者声称这将递归删除从最左下角开始的所有节点。但是不是free(leaf)只是释放叶指针的内存？是不是所有的节点仍然连接？清算如何进行？

来源

2016-06-07 Ambareesh S J

如何删除二叉树中的元素？一次只有零和零。 –

树被完全破坏，因此没有必要断开叶子。你可以断开它们，但它是没用的。你为什么不试试呢？ –

我建议你在纸上写下这张小图片，然后尝试使用这种算法释放它以获取它的一个挂图。我建议这种方法处理所有关于树木的事情 –

你是对的。它从C的“Allocated Memory”中回收内存，这很可能是堆。由于您正在删除树，因此它并不重要，因为它在树上递归时不能正确重构节点，因为它们即将被销毁。

此代码并未删除或从树中“移除”一个元素，它正在销毁给定叶节点的整个树。

从网站

的destroy_tree如下所示的实际上会释放所有的节点叶下存储的树节点：树。

来源

2016-06-07 09:13:34 ingramator

在你张贴的所有作者的链接有一棵树，看起来像这样：

递归删除功能的原理是一路下跌的左侧，然后然后右侧删除节点。因此，在下文中以上会发生（开始用含10的节点）

Node 10 -> leaf!=null -> destroy_leaf(leaf->left) 
    Node 6 -> leaf!=null -> destroy_leaf(leaf->left) 
    Node 5 -> leaf!=null -> destroy_leaf(leaf->left) 
     null -> do nothing and return back to Node 5 
    Node 5 - destroy_leaf(leaf->right) 
     null -> do nothing and return back to Node 5 
    free(Node 5) and return back to Node 6 
    Node 6 -> destroy->leaf(leaf->right) 
    Node 8 -> leaf!=null -> destroy_leaf(leaf->left) 
     null -> do nothing and return back to Node 8 
    Node 8 -> destroy_leaf(leaf->right) 
     null -> do nothing and return back to Node 8 
    free(node 8) and return back to Node 6 
    free(node 6) and return back to Node 10 
Node 10 -> destroy_left(leaf->right)

上面示出了如何函数将左侧从节点10向下递归作为节点是free d其父将指向已经释放的内存，但是这很好，因为当递归展开并释放父项时，最终会放弃父节点。

来源

2016-06-07 09:14:08 Sean

但是不是免费的（叶）只是返回叶指针的内存？

是的。但那不是全部。看看free的电话上面，你看到什么被称为？

并非所有节点仍然连接？

并不重要，因为...

如何结算发生？

的destroy_tree递归调用降下来左右，这将反过来做递归销毁，并在它释放结束，返回给调用者，这将释放等。最后，整棵树已经被释放。

来源

2016-06-07 09:16:30 datenwolf

我向您展示如何图形树会改变：

START：

    10 
      / \ 
       6  14 
      /\  /\ 
      free 8 11 18 

        10 
      / \ 
       6   14 
      / \  /\ 
      free free 11 18 


        10 
      /  \ 
       free  14 
      / \  /\ 
      free free 11 18 


        10 
       /  \ 
       free   14 
      / \  / \ 
      free free free 18 

        10 
       /  \ 
       free   14 
      / \  / \ 
      free free free free 

        10 
       /  \ 
       free   free 
      / \  / \ 
      free free free free 

        free 
       /  \ 
       free   free 
      / \  / \ 
      free free free free

当然到底，节点没有连接，他们不再存在。我只是在图片中展示了它们在算法过程中会如何改变。如果您还有其他问题，请随时询问。

我强烈建议你，每当你不明白树递归如何工作，在一张纸上写一个图片，然后像我上面写的低谷算法。

来源

2016-06-07 09:21:45

这是删除叶，它的分支在递归的方式。我为你画一个样本。圆圈中的数字显示叶子被释放的顺序。该线示出了代码的执行顺序

来源

2016-06-07 09:26:01 Alikbar

的free(leaf)呼叫释放，其被分配用于正在由指针leaf指向该变量的存储器。这里，它释放了struct node类型的变量占用的所有12个字节 - 即int value的4个字节，node *left指针的4个字节和node *right指针的4个字节。

通过调用destroy_tree(left)，您正在删除left指向的子树。你可以把它看作是放火烧到树顶，看着它从树叶上烧下来，先是左边的分支，然后是右边的分支。

来源

2016-06-07 10:32:02 2bigpigs

让我们试着从这个代码的理解：

void delete(struct node* node) 
{ 
if(node==NULL) 
return; 
delete(node->left); 
delete(node->right); 
free(node) 
}

在这段代码控制将转到最左边的叶子第一，它会从那里开始删除（如删除父母之前，我们必须先删除它的孩子）让我们来树例如：

所以首先对于节点4的存储器将被释放，然后对于节点5，作为游离不返回任何值（存储器参考被删除），从而母体节点也将指向NULL，s o 5 2后将被删除。我希望这可以帮助。

来源

2016-06-07 11:37:34 9codie05

但是第一个未定义节点的指针仍然指向一个正在请求段错误的释放节点，除非另有一层我们没有在这里看到，对吧？不完全确定，但它看起来像我 - 如果是这种情况，我一定会看到海报点。 – gbtimmon

如何删除C中二叉树中的元素？

回答

相关问题