0

我试图通过遍历树并根据需要删除内存来恢复树中分配的内存。例如，假设我有以下树结构：

struct tree
{
   int *value;
   tree *left;
   tree *right;
}

tree *root; //always points to the root of this tree

我知道我们必须value在每次递归调用后访问每个，删除它，然后移动到下一个节点（可以是leftor right），但是递归过程似乎非常违反直觉（特别是我们向左移动或移动到的部分正确的）。

我试图遵循“用根做某事，递归调用左边，然后递归调用右边”的规则，但代码的功能方式让我感到困惑。如何保留 的不变量root？如果有人可以用图片来解释这个概念，那就太好了。

4

2 回答 2

0

因为您需要在删除期间遍历树，所以想法是在返回时删除

void del_tree(tree *t) {

  if (t->left) {
    // there is a left subtree existing. delete it
    del_tree(t->left);  // first go deeper on left side
    // left branch now completely empty
    delete t->left;     // nothing left behind t->left
    t->left=0;          // just in case
  } else {
    // there is no left subtree existing
    // we are in a leaf or in an unbalanced node
  }

  if (t->right) {
    // there is a right subtree existing. delete it
    del_tree(t->right);  // now go deeper on right side
    // right branch now completely empty
    delete t->right;     // nothing left behind t->right
    t->right=0;          // just in case
  } else {
    // there is no rigt subtree existing
    // we are in a leaf or this was an unbalanced node
    // (before we deleted the left subtree)
  }

  // both branches are now completely empty
  // either they were from the beginning (leaf)
  // or we have successfully reduced this node to a leaf
  // now do the node visit

  if (t->value) {
    delete t->value;     // tidy up
    t->value=0;          // just in case
  }
  // now we are completely clean and empty
  // after return t will be deleted
}

void main() {
  tree *my_tree;

  // stuff

  del_tree(my_tree);   // delete the whole tree
  delete my_tree;      // delete the remaining root node
}

递归的一个非常重要的方面是何时停止。我假设结构中的 NULL 指针表示没有子树。

if (t->left) del_tree(t->left); 现在的策略是当我们在左右两边都达到 NULL 指针时尽可能深入，我们被困在一片叶子中。我们现在清理叶子（删除值）并返回。执行返回时delete t->left;，该节点在左子树上没有任何内容，并在其右子树上继续。

在这里我找到了一个很好的遍历图像

删除一棵树的问题分为3个部分。删除左子树，删除右子树，清理self。删除子树（左或右）与删除树本身的过程非常相似。所以你使用相同的函数，这称为递归。

考虑删除文件系统结构。您决定首先删除“左”文件夹结构的策略，然后删除子树“右”，最后删除文件“值”。当您在执行此策略期间更改为文件夹（无论是左还是右）时，您会注意到问题看起来相同。因此，您再次将此策略应用于树中的任何文件夹。

发生的情况是，除非当前目录中没有更多目录，否则您会反复切换到左侧目录。您删除文件“值”。然后您返回一个文件夹并删除名为“left”的文件夹。现在你寻找一个名为'right'的文件夹，进入它，找不到文件夹，删除文件'value'并返回到上一个文件夹。您删除了现在为空的“正确”，最后也删除了文件“值”。接下来是做进一步的返回（回溯）。等等。

在更深入的过程中，您无法删除非空文件夹。撤退时必须删除。

于 2012-12-09T00:17:17.677 回答
0

你可以把你的树想象成一棵有根和两片叶子的树，每片叶子都指向另一棵树的根。

事实上，这就是你如何保持“根的不变量”的方式，因为一旦你跟随叶子的指针，你就会到达另一棵树的根。

root -> branch -> leaf
|
V
branch -> leaf

也可以认为是

root -> tree1
|
V
tree2

反过来

root -> (root -> leaf)
|
V
(root -> leaf)

因此，当您遵循原始分支时，您最终会再次成为根。

于 2012-12-09T00:33:29.930 回答