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