为什么打印不会停止而没有错误？

Question

我尝试将布尔插入（k）的结果打印在for循环中，但是在第一次插入后，打印停止，这表明第二个插入并不完全成功。

内部方法插入（k），调用方法“检索（k）”，以检查是否已经插入k。

    for (int i = 100; i > 0; i--) {
        System.out.println(m.insert(i +1, 22));
        System.out.println("dd");
        System.out.println(m.retrieve(i+1).first + ",,,"+m.retrieve(i+1).second);
        System.out.println(i + " insertion done");
        System.out.println("---------");
    }

结果是

-------------------
true
dd
true,,,22
100 insertion done
---------
true
dd

在删除插入（）方法中的“检索（k）”调用之后，打印良好，所以我假设方法“检索（k）”存在问题，并且由于没有错误 + CPU使用率更高，它可能是无限循环，问题是，我看不到。

这是方法“检索（k）”

    public Pair<Boolean, T> retrieve(K k) {

    Pair<Boolean, T> ff = new Pair<Boolean, T>(false, null);
    BSTMapNode<K, T> p = root;
    if(root==null) {
        return new Pair<Boolean,T>(false,null);
    }
    else
    while (p != null) {
        if (k.compareTo(p.key) == 0) {
            ff.first=true;
            ff.second=p.data;
            return new Pair<Boolean,T>(true,p.data);
        } else if (k.compareTo(p.key) < 0) {
            p = p.left;
        } else
            p = p.right;
    }
    return new Pair<Boolean,T>(false,null);
}

编辑：添加的插入方法

public boolean insert(K k, T e) {
    BSTMapNode<K, T> p = current;
    BSTMapNode<K, T> q = current;
    // ISSUE HERE
    if (retrieve(k).first == true) {
        current = q;
        return false;
        //
    }
    BSTMapNode<K, T> tmp = new BSTMapNode<K, T>(k, e);
    if (root == null) {
        root = current = tmp;
        return true;
    } else {
        if (k.compareTo(current.key) < 0)
            current.left = p;
        else
            current.right = p;
        current = p;
        return true;
    }

Answer 1

问题是insert（）方法。当第二次调用时，root是非编号，因此执行进入Else分支。在那里，它设置current.left = p带有current == p，因此p现在是其自己的p.left代码>。当retrieve（）方法到达该节点时，它设置了p = p.left什么都没有改变，从而导致无限循环。

您使用当前节点的方法不起作用。在insert（）中，您每次都必须从根部搜索新节点的插入位置，类似于您在retive（）中所做的工作。只要继续下去直到到达叶子。然后将新节点插入其中。

代码看起来像这样：

public boolean insert (K key, T value) {
    if (root == null) {
        root = new BSTMapNode<>(key, value);
        return true;
    } else {
        BSTMapNode<K, T> p = root;
        while (true) {
            if (key.compareTo(p.key) == 0) {
                return false; // Already in BST
            } else if (key.compareTo(p.key) < 0) {
                if (p.left == null) {
                    p.left = new BSTMapNode<>(key, value);
                    return true;
                } else {
                    p = p.left;
                }
            } else {    
                // Analogous for right sub-tree
            }
        }
    }
}