c++ - 释放内存二叉树

Question

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

我还需要一个函数来释放构建树分配的内存。

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

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，我的建议是第一个解决方案。