2

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

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

无效插入（字符串）、布尔删除（字符串）和布尔查找（字符串）。

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

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

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

任何知识都非常感谢。

4

1 回答 1

2

一个节点被它的父节点引用（除了根，那个节点被你的 BST 本身引用）。为了从树中删除一个节点，您需要将该父节点中的引用设置为null.

你现在想要做的是这样的：

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

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

即当前引用null，但这不会更改父级（仅该局部变量）。

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

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

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

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

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
    }
}
于 2013-11-03T00:09:41.120 回答