Java实现BTS（二叉搜索树）增删方法报错求助

核心问题梳理 #

你的代码存在多个逻辑错误，导致编译/运行异常，主要问题如下：

1. 添加方法（addItem）的致命问题 #

• 无限循环隐患：未处理comparison == 0的情况（即待添加元素与当前节点相等），此时循环会一直停留在当前节点，导致程序卡顿。
• 节点链接错误：添加左子节点时，currentItem.setPrevious(item).setNext(currentItem)逻辑错误——你把新节点的next指向了父节点，不符合BST结构，叶子节点的左右子节点应设为null。
• 根节点初始化缺失：当树为空（root == null）时，代码直接跳过循环返回false，无法添加第一个节点。

2. 删除方法（removeItem）的逻辑漏洞 #

• 根节点处理不完整：仅将根节点替换为右子节点，完全忽略左子树，导致数据丢失。
• 非根节点处理片面：只处理了待删除节点是父节点右子节点的情况，未覆盖左子节点场景。
• 未处理多子节点情况：BST删除带两个子节点的节点时，需要用后继/前驱节点替换，你的代码完全没覆盖这种情况。
• 无效变量：定义了previous变量但从未使用，属于冗余代码。

修正后的代码实现 #

假设ListItem类包含compareTo、setPrevious、setNext、previous()、next()核心方法，以下是修正后的代码：

修正的addItem方法 #

@Override
public boolean addItem(ListItem item) {
    if (item == null) {
        return false;
    }

    // 树为空时直接设置根节点
    if (root == null) {
        root = item;
        item.setPrevious(null);
        item.setNext(null);
        return true;
    }

    ListItem currentItem = root;
    while (true) {
        int comparison = item.compareTo(currentItem);
        if (comparison > 0) {
            // 元素更大，放入右子树
            if (currentItem.next() != null) {
                currentItem = currentItem.next();
            } else {
                currentItem.setNext(item);
                item.setPrevious(null);
                item.setNext(null);
                return true;
            }
        } else if (comparison < 0) {
            // 元素更小，放入左子树
            if (currentItem.previous() != null) {
                currentItem = currentItem.previous();
            } else {
                currentItem.setPrevious(item);
                item.setPrevious(null);
                item.setNext(null);
                return true;
            }
        } else {
            // 元素已存在，不重复添加
            return false;
        }
    }
}

修正的removeItem方法 #

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

    ListItem currentItem = root;
    ListItem parent = null;
    int comparison;

    // 先定位待删除节点
    while (currentItem != null) {
        comparison = item.compareTo(currentItem);
        if (comparison > 0) {
            parent = currentItem;
            currentItem = currentItem.next();
        } else if (comparison < 0) {
            parent = currentItem;
            currentItem = currentItem.previous();
        } else {
            // 找到目标节点，退出循环处理删除
            break;
        }
    }

    // 未找到待删除节点
    if (currentItem == null) {
        return false;
    }

    // 情况1：待删除节点是叶子节点
    if (currentItem.previous() == null && currentItem.next() == null) {
        if (currentItem == root) {
            root = null;
        } else if (parent.previous() == currentItem) {
            parent.setPrevious(null);
        } else {
            parent.setNext(null);
        }
        return true;
    }

    // 情况2：待删除节点只有右子节点
    else if (currentItem.previous() == null) {
        if (currentItem == root) {
            root = currentItem.next();
        } else if (parent.previous() == currentItem) {
            parent.setPrevious(currentItem.next());
        } else {
            parent.setNext(currentItem.next());
        }
        return true;
    }

    // 情况3：待删除节点只有左子节点
    else if (currentItem.next() == null) {
        if (currentItem == root) {
            root = currentItem.previous();
        } else if (parent.previous() == currentItem) {
            parent.setPrevious(currentItem.previous());
        } else {
            parent.setNext(currentItem.previous());
        }
        return true;
    }

    // 情况4：待删除节点有两个子节点，用右子树最小节点（后继）替换
    else {
        ListItem successor = currentItem.next();
        ListItem successorParent = currentItem;

        // 找到右子树的最左节点（最小元素）
        while (successor.previous() != null) {
            successorParent = successor;
            successor = successor.previous();
        }

        // 替换待删除节点的位置
        if (currentItem == root) {
            root = successor;
        } else if (parent.previous() == currentItem) {
            parent.setPrevious(successor);
        } else {
            parent.setNext(successor);
        }

        // 清理后继节点的原位置
        if (successorParent != currentItem) {
            successorParent.setPrevious(successor.next());
        } else {
            successorParent.setNext(successor.next());
        }

        // 继承待删除节点的左右子树
        successor.setPrevious(currentItem.previous());
        successor.setNext(currentItem.next());

        return true;
    }
}

关键说明 #

• 若需要子节点指向父节点，建议给ListItem添加parent字段，可简化删除操作中父节点的查找逻辑。
• BST核心规则：左子树所有节点值小于父节点，右子树所有节点值大于父节点，所有操作必须遵守该规则。

内容的提问来源于stack exchange，提问作者איתי גולדשטיין