c++ - 释放内存 二叉树

Question

我有一个创建二叉树的函数(*build_tree)* (Huffman)。

我还需要一个函数来释放 build tree 分配的内存。

这是我第一次使用二叉树，所以我有点困惑。我应该创建一个循环遍历树中的每个节点并将其删除吗？我应该考虑节点是叶节点还是父节点？

void free_memory(NodePtr root)
{
    delete root;
}

struct HuffmanNode
{
   //some stuff
    HuffmanNode *left;
    HuffmanNode *right;
};

如果有人能帮助我开始，我将不胜感激:)

Answer 1

如果您使用智能指针，问题会自行解决。如果每个节点都包含一个私有(private) SP 到它的子节点，并且您删除一个节点，它的所有子节点也将被释放。显然，您的类析构函数在清理时会被 SP 调用，需要释放任何其他非 RIIA 分配的资源(如果存在的话)。

class Node
{
private:
   std:unique_ptr<Node> left;
   std:unique_ptr<Node> right;
}

我正在使用 std::unique_ptr<>在这里是因为我假设这些是私有(private)的并且不会暴露给程序的其他部分。如果你想让其他东西使用这些指针来引用节点，那么你应该使用 std::shared_ptr<> .

如果您不使用 SP，那么类析构函数需要自己完成工作，您必须更加小心内存泄漏。每个类的析构函数都会删除其子类，而子类又会在每个子类中调用析构函数。

class Node
{
private:
  NodePtr left;
  NodePtr right;

  ~Node()
  {
     delete left;
     delete right;

     // Delete any other resources allocated by the node.
  }
}

您也可以按照@OldProgrammer 的建议进行操作，并从下往上遍历树并删除节点。请记住，您必须自下而上地执行此操作。如果您自上而下地执行它，那么您将丢失对(尚未)未删除的子节点和泄漏内存的引用。如您所见，递归删除代码 (as referenced in @unluddite's answer) 复杂得多。

递归地做(任何事情)都会有内存开销。请参阅:Is a recursive destructor for linked list, tree, etc. bad? .如果你的树很大，那么你应该考虑这一点并进行相应的测试。

如果您可以使用 SP，我的建议是第一个解决方案。