如何正确添加二叉搜索树中的节点？

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