我try 在for循环中打印布尔插入(K)的结果,但在第一次插入后,打印停止,这表明第二次插入没有完全成功.

在方法insert(K)中,调用方法"retrieves(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

删除insert()方法中的"retrieves(K)"调用后,打印运行正常,因此我假设"retrieves(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;
    }

推荐答案

问题在于insert()方法.当第二次调用它时,root是非null的,因此执行进入else分支.在那里,它将current.left = pcurrent == p结合起来,所以p现在是它自己的p.left.当retrieve()方法到达该 node 时,它设置p = p.left,这不会改变任何内容,从而导致无限循环.

使用current node 的方法不起作用.在insert()中,每次都必须从根搜索新 node 的插入位置,类似于在retrieve()中所做的操作.继续往下走,直到你找到一片叶子.然后在那里插入新 node .

代码可能如下所示:

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

Java相关问答推荐

从技术上讲,OPC UA客户端是否可以通过转发代理将请求通过 tunel 发送到OPC UA服务器?

Character::Emoji不支持带数字的字符吗?

内存中的H2修剪尾随空格

Spring data JPA/Hibernate根据id获取一个列值

使用GridBagLayout正确渲染

try 判断可选参数是否为空时出现空类型安全警告

迁移到Java 17后,日期显示不准确

是否为计划任务补偿系统睡眠?

舰队运行配置Maven版本

从泛型枚举创建EnumMap

如何在不作为类出现的表上执行原生查询?

如何在IntelliJ IDEA的Build.sbt中添加外部JAR文件?

Java返回生成器的实现

Android上的SQLite:Android.database.SQLite.SQLiteReadOnlyDatabaseException:try 写入只读数据库(代码1032 SQLite_readonly_DBMOVED)

Java 21保护模式的穷尽性

在输入端没有可行的替代方案'; Select *';

JAVA 正则表达式识别字符串string或字符串内的字符char

有没有办法仅将 JComboBox 中的选定项目居中(因此保持组合框中的所有项目左对齐)

jpackage 之后如何使图像、属性和其他资源可供我的模块化应用程序使用?

防止屏幕转换后重叠?