c++ - 如何删除树的孩子

Question

我需要删除除根之外的前缀树的所有子级。我不问任何代码。我只需要一种方法来遍历和删除树的所有子节点。

Answer 1

您可以使用后序遍历来遍历树并删除节点，如下所示：

function deleteTree(node, tree_root) {
     if (node != null) {
         // recursively delete left sub-tree.
         deleteTree(node->left, tree_root);

         // recursively delete right sub-tree.
         deleteTree(node->right, tree_root);

         // time to delete the node..but only if it's not root.
         if( node != tree_root) {
              delete node;
         }  
     }
}

并将上述函数调用为：

deleteTree(root,root);

Answer 2

编写一个方法delete，它接受一个树节点：

 for each child in node
   call delete on child
   remove child from node
   free child

对于 root 的每个孩子调用这个删除方法。

Answer 3

有趣的是，你可能会做一些优雅的事情——删除后可能不会使用树，所以你可以编写一个节点的析构函数：

struct Node // Non-copyable!
{
  Node *left, *right;

  Node()
    : left(NULL)
    , right(NULL)
  {
  }
  ~Node()
  {
    delete left;
    delete right;
  }
};

就这样！你用它：delete root. 请注意，您之前可能不会测试 NULL，delete因为它在 C++ 标准下运行良好（只是返回）。