如何正確添加二叉搜索樹中的節點？

Question

這是我的代碼

public boolean insertWord(String key, String meaning) { 

    if((root == null)){ 
     root = new TreeNode(); 

     root.key = key; 
     root.meaning = meaning; 
    } 


    else{ 

     TreeNode subroot = root; 

     if(subroot.key.compareTo(key) == 0){ 
      return false; 
     } 
     else if(key.compareTo(subroot.key) < 0){ 

      if(subroot.left != null){ 
       subroot = root.left; 
       return insertWord(key, meaning); 
      } 
      else{ 
       subroot.left = new TreeNode(); 
       subroot.left.key = key; 
       subroot.left.meaning = meaning; 
      } 

     } 
     else{ 
      if(subroot.right != null){ 
       subroot = root.right; 
       return insertWord(key, meaning); 
      } 
      else{ 
       subroot.right = new TreeNode(); 
       subroot.right.key = key; 
       subroot.right.meaning = meaning; 
      } 

     } 
    } 

    return true; 
} 

這樣做給我計算器錯誤。有人可以幫助我瞭解爲什麼我一直在收到這個錯誤。我知道它是因爲無限循環，但我不知道它爲什麼會發生。有人能告訴我它在哪裏發生，以及如何解決它？謝謝

Answer 1

在下面的代碼中，如果subroot設置爲root.left那麼您不應該再使用subroot的密鑰嗎？你在哪裏傳遞這些信息？

if(subroot.left != null){ 
     subroot = root.left; 
     return insertWord(key, meaning); 
} 

現在我提出我的版本，我已經實現：

protected Node<T> insertValue(T value) { 
    Node<T> newNode = getNewNode(value); 

    // If root is null, assign 
    if (root == null) { 
     root = newNode; 
     size++; 
     return newNode; 
    } 

    Node<T> currentNode = root; 
    while (currentNode != null) { 
     if (newNode.getData().compareTo(currentNode.getData()) <= 0) { // Less than or equal to goes left 
      if(currentNode.getLeft() == null) { 
       insertNodeToLeft(currentNode, newNode); 
       break; 
      } 
      currentNode = currentNode.getLeft(); 
     } else {          // Greater than goes right 
      if (currentNode.getRight() == null) { 
       insertNodeToRight(currentNode, newNode); 
       break; 
      } 
      currentNode = currentNode.getRight(); 
     } 
    } 

    return newNode; 
} 

希望它會幫助你。

Answer 2

正如Aaron指出的那樣，您需要更新下一步要比較的新密鑰。在你的代碼中，如果left節點爲null，則插入節點，但如果它不爲null，則需要將您的密鑰與此新節點的密鑰進行比較。這個代碼在哪裏？

else if(key.compareTo(subroot.key) < 0){ 

      if(subroot.left != null){ 
       subroot = root.left; 
      // WHERE ARE YOU USING KEY OF THIS NEW NODE subroot FOR COMPARISON? 
      return insertWord(key, meaning); 
     } 
     else{ 
      subroot.left = new TreeNode(); 
      subroot.left.key = key; 
      subroot.left.meaning = meaning; 
     } 

    } 

編輯：對方法的實現要插入左，正確的應該是類似的東西：

private void insertNodeToLeft(Node<T> parent, Node<T> child) { 
    // New left node 
    parent.setLeft(child); 
    child.setParent(parent); 
    size++; 
} 

private void insertNodeToRight(Node<T> parent, Node<T> child) { 
    // New right node 
    parent.setRight(child); 
    child.setParent(parent); 
    size++; 
}