假设我有一棵树，如下所示：
8
3 12
4 5 6 15
1 2
如果我想删除 3，请将其替换为左下角的节点（在本例中为 1）。然后，在该图中，2 将附加到 4。
我将如何编码？
我知道您必须通过某种循环一直遍历左侧，然后适当地重置每个指针。此外，您必须考虑最后一个左节点可能有右孩子的情况。
问问题
517 次
1 回答
0
在我们解决“如何”之前，有两件事：
(1) - 这是次要的。这个问题仅在二叉搜索树（BST）的上下文中才有意义，而不仅仅是二叉树。而且这棵树不是 BST，因为 3 和 4 交换了。
(2) - 任何时候您对 BST 执行删除操作，并且想要“修复”树以使生成的树也是 BST，您有两个选择：(a) 您可以选择要删除的节点的左子树，或者（b）您可以选择要删除的节点的右子树中的最小值，并将其与要删除的节点交换。（您应该说服自己为什么这些选项都会给您留下 BST）。在您的示例中（正确放置 3 和 4），这意味着将 4 与 3 或 5 交换。
现在是“如何”做到这一点。假设我们从上面选择了选项 (a)。你需要做的是编写一个函数，从 4 开始，向左走一步，然后尽可能地向右移动（你还应该说服自己为什么这是正确的）。一旦你不能再向右遍历，你就知道你在左子树中找到了最大值。然后，将这个值替换为要删除的节点，然后删除刚刚取值的节点。
如果您已经知道如何对您在此处展示的树进行编码，那么这实际上是非常简单的编码。如果您有特定于代码的问题，请提供更多详细信息
于 2012-08-21T23:52:22.360 回答