java - 递归二叉搜索树删除方法

Question

首先，这是家庭作业，所以把它放在那里。

我应该用特定的方法实现一个二叉搜索树:

void insert(String)、boolean remove(String) 和 boolean find(String)。

我已经能够成功编程和测试插入和查找方法，但在删除时遇到困难。

在我的程序中发生的事情是删除实际上并没有从树中删除任何东西，我相信这是因为它只引用当前节点的本地创建，但我可能是错的。我想我可以实现我需要测试的不同案例的逻辑(可能需要帮助删除一个有两个 child 的节点案例，但我想我在概念上明白了)主要是想了解我需要做些什么来引用树妥妥的在

current = null; // case

这是我到目前为止得到的:

public boolean remove(String title)
{
    return remove(root, title);
}
private boolean remove(BSTNode current, String title)
{
    if (current == null)
    {
        return false;
    }
    if (current.data == title)
    {
    if (current.left_child !=null && current.right_child != null)
    {
        return true;  // returning true since I haven't finished writing this case
    }
    else if (current.left_child == null && current.right_child == null)
        {
        current = null;  // this should remove the node from tree but it doesn't
        return true; 
    }

    else if (current.left_child != null && current.right_child == null)
    {
        current = current.left_child;    // don't think this is right
        return true;
    }
    else if (current.right_child != null && current.left_child == null)
    {
        current = current.right_child;   // not sure about this
        return true;
    }

    }
root = current;
if (title.compareToIgnoreCase(current.data) == -1)
{
    return remove(current.left_child, title);
}
    else 
{
    return remove(current.right_child, title);
}
}

非常感谢任何知识。

Answer 1

一个节点由它的父节点引用(除了根节点，该节点由您的 BST 本身引用)。为了从树中删除节点，您需要将父节点中的引用设置为 null。

你现在要做的是:

Before:
parent.left ---> node <--- current

After setting current = null:
parent.left ---> node      current ---> null

也就是说，当前引用 null，但这不会更改父级(仅那个局部变量)。

在您的 remove 方法中，您还需要传递父项(或者在调用父项时处理两个子项，无论您喜欢什么)。

顺便说一句:从不，永远将字符串与== 进行比较，例如参见this question .

---

如何找到节点及其父节点而不在每个节点中显式存储父节点:

我会说在循环中执行此操作比使用递归更简单，但两者都可以。在一个循环中:

BSTNode parent = null;
BSTNode current = root;
boolean found = false;
while (!found && current != null) {
    int compare = title.compareToIgnoreCase(current.data);
    if (compare == 0) {
        found = true;
    } else {
        parent = current;
        if (compare < 0) {
            current = current.left;
        } else {
            current = current.right;
        }
    }
}
if (!found) {
    // title was not found
} else if (parent == null) {
    // found the root
} else {
    // found another node
}

递归很烦人，因为您需要一个既返回节点又返回其父节点的方法。您将需要一些简单的内部类来解决这个问题:

private class NodeAndParent {
    public BSTNode node;
    public BSTNode parent;
    public NodeAndParent(BSTNode node, BSTNode parent) {
        this.node = node;
        this.parent = parent;
    }
}

private boolean find(String title, NodeAndParent current) {
    if (current.node == null) {
        return false; // not found
    } else {
        int compare = title.compareToIgnoreCase(current.node.data);
        if (compare == 0) {
            return true; // found
        } else {
            current.parent = current.node;
            if (compare < 0) {
                current.node = current.node.left;
            } else {
                current.node = current.node.right;
            }
        }
    }
}

private boolean remove(String title) {
    NodeAndParent nodeAndParent = new NodeAndParent(root, null);
    boolean found = find(title, nodeAndParent);
    if (!found) {
        // title was not found
    } else if (nodeAndParent.parent == null) {
        // found the root
    } else {
        // found another node
    }
}