c++ - 遍历二进制搜索树C++

我正在进行编程任务，并编写了一堆函数来实现二进制搜索树，并给出了一些函数。我以为我了解递归，但是如果您愿意的话，我会一直卡在切换方向上。

这是赋值给定的函数:

static void deleteAll(BSTNode<Data>* n) {
  if (0 == n) return;
  deleteAll(n->left);
  deleteAll(n->right);
  delete n;
}

要删除一棵很短的树，

根
/ \
左撇子

我叫deleteAll(root)。 n != 0，所以现在我叫deleteAll(lefty)。 n != 0，所以我叫deleteAll(lefty->left)。当然没有左节点。当我添加lefty节点时，我的构造函数将left，right和parent指针初始化为0，所以现在是n == 0。因此，我退出该函数，从不删除正确的代码。我如何到达deleteAll(n->right)？

如我所说，提供了此功能，所以我不应该更改它。我以为可能必须调用deleteAll(b.begin())或b.end()才能从最左边或最右边的节点开始，但是每次想到时，我都会碰到n == 0。

请帮助我理解。

最佳答案

想象有一个箭头指向正在执行的当前行。当我们调用deleteAll(root)时，首先我们检查root是否为0:

--> if (0 == root) return;
    deleteAll(root->left);
    deleteAll(root->right);
    delete root;

因为是root != 0，所以我们将其称为deleteAll(root->left):

    if (0 == root) return;
--> deleteAll(root->left); /*
    |-1-> if (0 == lefty) return;
    |-2-> deleteAll(lefty->left);
    |-3-> deleteAll(lefty->right);
    |-4-> delete lefty; */
    deleteAll(root->right);
    delete root;
  }

现在，箭头将移回到函数顶部，并开始对lefty执行相同的操作，并通过我的注释中的1-4行运行(在第2行，将再次进行相同的扩展，直到找到空节点) 。但是这里重要的是它记住函数调用之前的位置，以便以后可以恢复。因此，deleteAll(root->left)将执行其操作并最终返回。然后原始 call 继续:

    if (0 == root) return;
    deleteAll(root->left);
--> deleteAll(root->right);
    delete root;

现在，右节点也被删除。这发生在递归的每一步。请记住，return仅返回当前函数之外的内容，而不返回整个递归链。

关于c++ - 遍历二进制搜索树C++，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/12736649/