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

Question

我有一个在Java中的二叉搜索树作业，我给了完整的树和节点类以及一个SearchTree类，我将在其中完成搜索和插入方法。该搜索应该返回与搜索到的键相对应的节点的值。

Here是Tree类和here的Node类。我的搜索和插入方法如下。

看来我越来越接近了，但是在Tree [Node [0,1，null，null]]中插入关键字0和值2会导致Tree [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; 
}