递归二叉搜索树删除方法

Question

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

我应该用特定的方法实现二叉查找树：

void insert（字符串）、boolean remove（字符串）和boolean find（字符串）。

我已经能够成功地编程和测试插入，并找到方法，但我有困难与删除。

我的程序中发生的事情是，删除实际上并没有从树中删除任何东西，我相信这是因为它只引用当前节点的本地创建，但我可能错了。我认为我可以实现我需要测试的不同案例的逻辑（可能需要帮助删除具有两个子节点的案例，但我认为我在概念上得到了它）主要是试图理解我需要做什么不同的事情来正确引用树

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，但这不会更改父变量（仅更改该局部变量）。

在删除方法中，您还需要传递父级（或者在父级调用中处理两个子级，无论您更喜欢什么）。

顺便说一下：永远不要将字符串与==进行比较，例如，请参见这个问题。

如何在不将父节点显式存储在每个节点中的情况下查找节点及其父节点：

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

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
}

By递归很烦人，因为您需要一个同时返回节点及其父节点的方法。您需要一些简单的内部类来解决这个问题：

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
    }
}