二元樹沒有插入到任何節點的右側，是另一個節點的左側子節點

Question

我的二叉樹的當前插入方法未插入到其父節點的左側子節點的右側。 當前代碼：

private BinaryTreeNode insert(BinaryTreeNode current, String word) { 
    if (current == null) { 
     current = new BinaryTreeNode(word); 
    } else { 
     if (word.compareToIgnoreCase(current.value) < 0) { // if smaller than current node 
      if (current.left != null) { 
       if (word.compareToIgnoreCase(current.left.value) < 0) {// check next node for lesser than, 
        current.left = (insert(current.left, word)); 
       } 
      } else { 
       current.left = new BinaryTreeNode(word);// iff current node is end of tree 
       System.out.println(word + "left"); 
      } 
     } else { 
      if (current.right != null) { // if larger than current node 
       current.right = (insert(current.right, word)); 
      } else { 
       current.right = new BinaryTreeNode(word); // if current node is end of tree 
       System.out.println(word + "right"); 
      } 
     } 
    } 
    return current; 
} 

Answer 1

你的問題就在這裏：

if (word.compareToIgnoreCase(current.left.value) < 0) {// check next node for lesser than, 
    current.left = (insert(current.left, word)); 
} 

什麼是你希望這個做什麼？你已經知道你應該插入到當前節點的左側，但爲什麼你要重新檢查下一個節點呢？

Answer 2

你應該遞歸的，而不是一直垂到比較向左：

private static BinaryTreeNode insert(BinaryTreeNode current, String word) { 
    if (current == null) { 
     current = new BinaryTreeNode(word); 
    } else { 
     int test = word.compareToIgnoreCase(current.value); 
     if (test < 0) { 
      current.left = insert(current.left, word); 
     } else if (test > 0) { 
      current.right = insert(current.right, word); 
     } 
     // else word already at this node! 
    } 
    return current; 
} 

注意，功能應該是靜態的，因爲它不依賴於this。

Answer 3

我覺得有一些錯誤...我會做這樣的事情：

private void insert(BinaryTreeNode current, String word) { 
    if (current == null) { 
     current = new BinaryTreeNode(word); 
    } else { 
     if (word.compareToIgnoreCase(current.value) < 0) { 

      if (current.left != null) { 
       insert(current.left, word); 
      } else { 
       current.left = new BinaryTreeNode(word); 
       System.out.println(word + "left"); 
      } 

     } else { 

      if (current.right != null) { 
       insert(current.right, word); 
      } else { 
       current.right = new BinaryTreeNode(word); 
       System.out.println(word + "right"); 
      } 

     } 
    } 
}