二叉搜索树insert方法异常导致中序遍历输出顺序错误问题求助

数据老陈

2026-9-23

BST插入功能错误修复方案

核心错误原因

insert方法查找插入位置时没有从根节点出发，而是基于类成员变量current的遗留值遍历，导致新节点挂载位置完全不符合BST的结构规则，因此中序遍历输出顺序错误。

具体错误点

原insert初始化遍历指针时错误使用current赋值：BSTNode<T> p = current, q = current;，current是之前操作的残留位置，不是整棵树的根节点，无法遍历到正确的插入位置
挂载新节点时错误使用current作为父节点，而非遍历过程中记录的实际父节点

修复后的insert代码

public boolean insert(int key, T val) {
    // 每次插入都从根节点开始遍历找位置
    BSTNode<T> p = root, q = root;

    while (p != null) {
        q = p;
        if (p.key == key) {
            // 重复key插入失败
            return false;
        } else if (key < p.key)
            p = p.left;
        else
            p = p.right;
    }

    BSTNode<T> newNode = new BSTNode<T>(key, val);
    if (empty()) {
        root = current = newNode;
        return true;
    } else {
        // 用遍历得到的父节点q挂载新节点
        if (key < q.key)
            q.left = newNode;
        else
            q.right = newNode;
        current = newNode;
        return true;
    }
}