二叉树，从树中移除节点后删除节点

Question

我正在实施 AVL 树。从树中删除节点按预期工作，例如如果我删除节点的左叶节点，左子节点将指向 nullptr。

但是，由于该节点（现已删除）曾经是使用 'new'-关键字创建的，是否有必要以某种方式释放它占用的内存？我的节点看起来像这样：

    struct Node {
       const int key;
       short balance = 0;
       Node* left = nullptr;
       Node* right = nullptr;

       Node(const int key);
       Node(const int key, Node *left, Node *right);
       ~Node();
    }

我的意思是：即使删除的节点不再包含在树中，例如没有任何东西指向它，它是否会 'out of scope' 并自动从内存中删除？或者我是否必须将它的 right/left-pointers 设置为 nullptr？

谢谢！

Answer 1

However, since that (now removed) node was once created with the 'new'-> keyword, is it necessary to somehow free the memory it takes up?

这不是强制性的，但如果你想避免在某个时候吃掉你所有的内存，那么是的，你需要这样做，你可以使用 delete 关键字

What I am saying is: even tho the removed node is not included in the tree anymore, e.g. nothing is pointing to it, does it go 'out of scope' and is removed from memory automatically?

不，c++

中没有垃圾收集器

有更多 "modern" 方法来做你正在做的事情，但我觉得这更像是一种学习练习，在这种情况下，将你的 delete 电话与你的 [=13] 相匹配=] 手动调用是了解正在发生的事情的好方法。如果需要，您可以搜索 "smart pointers".

Answer 2

简而言之：是的。你必须释放内存。据我所知，C++ 只会自动为没有 'new' 声明的对象释放内存。它们作为函数 returns 被删除。您可以使用删除节点函数 return 删除节点的内存地址，或者一旦找到就在函数内删除它。

澄清一下，不，你不需要必须释放任何内存，因为它在程序退出时被释放，但是一旦程序或其执行时间增长。

二叉树，从树中移除节点后删除节点

Binary tree, delete Node after removing it from the tree

c++

memory

tree

avl-tree