BTS - 二叉树搜索

Question

我正在尝试用 java 创建我的第一个 BTS，但我的代码遇到一些问题：

我需要创建用于添加项目和从树中删除项目的方法。

这是我写的：

@Override
public boolean addItem(ListItem item) {
    if(item == null){
        return false; // nothing is inside
    }
    ListItem currentItem = root;
    while(currentItem != null){
        int comparison = item.compareTo(currentItem);
        if(comparison > 0){
            if(currentItem.next() != null){
                currentItem = currentItem.next();
            }
            else{
                currentItem.setNext(item).setPrevious(currentItem);
                return true;
            }
        }
        if(comparison < 0){
            if(currentItem.previous() != null){
                currentItem = currentItem.previous();
            }
            else{
                currentItem.setPrevious(item).setNext(currentItem);
                return true;
            }
        }
    }
    return false;
}

@Override
public boolean removeItem(ListItem item) {
    if (item == null || root == null) {
        return false;
    }
    ListItem currentItem = root;

    while (currentItem != null) {
        ListItem previous = currentItem;
        int comparison = item.compareTo(currentItem);
        if (comparison > 0) {
            if (currentItem.next() != null) {
                currentItem = currentItem.next();
            } else {
                return false;
            }
        } else if (comparison < 0) {
            if (currentItem.previous() != null) {
                currentItem = currentItem.previous();
            } else {
                return false;
            }
        } else {
            if (currentItem == this.root) {
                this.root = currentItem.next();
            } else {
                currentItem.previous().setNext(currentItem.next());
                return true;
            }
        }
    }
    return false;
}

我的代码有什么问题吗？它无法正确编译并卡住。 :(

我不明白如何使右链接和左链接引用父节点。

Answer 1

根据所提供的代码，我采用

ListItem

的属性

previous

和

next

来引用其子节点 -

previous

为较小项目子树的根，

next

为根更大项目的子树。正如我在评论中所写，这是非常规的命名，可能会让其他人感到困惑。我怀疑它也可能让你感到困惑。

使用

left

和

right

或从它们派生的东西会更传统。如果您想用简洁一点来换取更清晰一点的话，也许可以使用

leftChild

和

rightChild

。

了解了这一点后，

addItem()

中的这些行看起来是错误的：

                currentItem.setNext(item).setPrevious(currentItem);

                currentItem.setPrevious(item).setNext(currentItem);

尚不清楚

setNext()

和

setPrevious()

返回什么，但唯一有意义的选项是调用它们的项目或设置为子项的项目。无论哪种方式，您都会创建一个循环，要么

currentItem

直接回到自身，要么

currentItem

到

item

，然后

item

回到

currentItem

。这可以很容易地解释树上无限循环的后续操作。也许你想要的只是：

                currentItem.setNext(item);

和

                currentItem.setPrevious(item);

.

本着这种精神，你评论说

我不明白如何使右链接和左链接引用父节点。

很可能，你不。尽管二叉搜索树可以具有从子级到父级的链接，但这对于标准 BST 操作来说并不是必需的，并且许多 BST 没有这样的链接。如果你的树有它们/想要它们，那么这将是这些物品的不同属性，而不是

next

或

previous

。

假设您确实没有父链接，则您的

removeItem()

应该在遍历树时在单独的变量中 track 当前节点的父节点。看起来您有一个变量

previous

可能是用于此目的，但您没有使用它并且它的范围不合适。您可能想要更多类似的东西：

    ListItem parentItem = null;
    ListItem currentItem = root;

    while (currentItem != null) {
        int comparison = item.compareTo(currentItem);

        if (comparison > 0) {
            parentItem = currentItem;
            currentItem = currentItem.next();
        } else if (comparison < 0) {
            parentItem = currentItem;
            currentItem = currentItem.previous();
        } else {
            // ... remove the node ...
            return true;
        }
    }
    return false;
}

然后您可以（并且需要）在实际的节点删除中使用

parentItem

。

另请注意：

• 您的

  addItem()

  似乎无法将项目添加到空树中，因为如果树

  false

  最初为空，它将返回

  root

  而不执行任何操作。

• 问题中实际的节点删除代码，

  currentItem.previous().setNext(currentItem.next());
  

  不太正确。跟踪和使用父项在这里是必要的，但还不够。考虑

  currentItem.previous()

  的原始右子树会发生什么。如果它有一个（很可能），那么它就会丢失。