Java二叉搜索树-工作不正确的插入方法

Question

我有一个Java中的二叉搜索树作业，其中给了我完整的树和节点类，还有一个SearchTree类，我要在其中完成搜索和插入方法。搜索应该返回对应于所搜索键的节点的值。

这里是树类，这里是节点类。我的搜索和插入方法如下。

看来我已经接近了，但是将键0和值2插入树[node[0,1,null,null]]的测试结果是树[node[0,1,null,null]]而不是正确的树[node[0,2,null,null]]。这里我有什么不理解的？

public static Object search(Tree tree, int key) {
    Node x = tree.getRoot();
    while (x != null) {
        if (key == x.getKey()) {
            return x.getValue();
        }
        if (key < x.getKey()) {
            x = x.getLeft();
        } else {
            x = x.getRight();
        }            
    }
    return null;
}

public static void insert(Tree tree, int key, Object value) {
    if (tree.getRoot() == null) {
        tree.setRoot(new Node(key, value));
    }
    Node juuri = tree.getRoot();
    while (juuri != null) {
        if (key == juuri.getKey()) {
            return;
        } else if (key < juuri.getKey()) {
            if (juuri.getLeft() == null) {
                juuri.setLeft(new Node(key, value));
                return;
            } else {
                juuri = juuri.getLeft();
            }
        } else {
            if (juuri.getRight() == null) {
                juuri.setRight(new Node(key, value));
                return;
            } else {
                juuri = juuri.getRight();
            }
        }
    }
}

Answer 1

我看到的问题是，你的树中的关键值是唯一的。在这个if语句中，如果您看到键已经在树中，则保留insert方法而不添加节点。

 if (key == juuri.getKey()) { 
      return;
 }

在您的示例中（如果我理解正确的话），0已经在树中，所以再次插入0时没有任何变化。基于您的示例，我假设您希望在密钥相同的情况下对节点进行更新。所以这段代码可以做到这一点。

if (key == juuri.getKey()) {
     juuri.setValue(value);
     return;
}