BST只保留最后插入的值并使其成为根

Question

我试图使用insert（）填充二叉查找树，但是当每次“打印”我的BST的内容时，我只收到最后一项插入BST。我需要解决什么问题才能确保我的所有价值都保留在BST中？

从调试，我认为我的问题是，我的公共无效插入（）是设置新的价值为根加班它被称为。我不知道如何解决它？

这里是我的BST类：

public class BinarySearchTree<T extends Comparable<T>> { 

private class BinarySearchTreeNode<E>{ 
    public BinarySearchTreeNode<E> left, right; 
    private E data; 

    private BinarySearchTreeNode (E data) { 
     this.data = data; 
    } 
} 

private BinarySearchTreeNode<T> root; 

public boolean isEmpty() { 
    return root == null; 
} 
private BinarySearchTreeNode<T> insert(T value, BinarySearchTreeNode<T> ptr) { 
      if (ptr == null){ 
     ptr = new BinarySearchTreeNode<>(value); 
     return ptr; 
    } 
    int compare = value.compareTo(ptr.data); //when ptr != null, this line and below should execute for each bstStrings.inster(x) 
    /* pass the value (s1...sN) when compared to (ptr.data) to compare 
    * when value and ptr.data == 0 re 
    */ 
    if (compare == 0) { 
     return ptr; 
    } 
    if (compare < 0) { 
     while (ptr.left != null){ 
      ptr = ptr.left; 
      if (ptr.left == null) {//found insertion point 
       BinarySearchTreeNode<T> node = new BinarySearchTreeNode<>(value); 
       ptr = ptr.left; 
       ptr = node; 
       return ptr; 
      } 
     } 
    } 
    else { 
     return insert(value, ptr.left); 
    } 
    if (compare > 0) {    
     if (ptr.right == null) { 
      BinarySearchTreeNode<T> node = new BinarySearchTreeNode<>(value); 
      ptr = ptr.right; 
      ptr = node; 
      return ptr; 
     } 
    } 
    else { 
     return insert(value, ptr.right);      
    } 
    return ptr; 
} 
public void insert(T value) { 
    root = insert(value, root); //****Where I believe the problem is****** 
} 
private void printTree(BinarySearchTreeNode<T>node){ 
    if(node != null){ 
     printTree(node.left); 
     System.out.println(" " + node.data); 
     printTree(node.right); 
    } 
} 
public void printTree(){ 
    printTree(root); 
    System.out.println(); 
}  
} 

为了增加背景下，这里是我的Main（）我在哪里调用插件（），并试图插入串入BST：

public class Main { 

public static void main(String[] args) { 

    BinarySearchTree<String> bstStrings = new BinarySearchTree<String>(); 

    String s = "Hello"; 
    String s1 = "World"; 
    String s2 = "This Morning"; 
    String s3 = "It's"; 

    bstStrings.insert(s); 
    bstStrings.insert(s1); 
    bstStrings.insert(s2); 
    bstStrings.insert(s3); //the only inserted value that is printed below 

    bstStrings.printTree(); 

     System.out.println(); 
     System.out.println("You should have values above this line!"); 
} 
} 

最后我的控制台输出：

It's 


You should have values above this line! 

Answer 1

一些提示：

• 我在insert里面看不到任何递归调用。如果没有适当的递归调用（基于该值的当前节点的左侧或右侧子树），你将如何遍历BST？我看到一些注释掉的代码看起来像会执行这些调用。他们为什么被评论出来？
• 您将返回新插入的节点，然后将其设置为root。这会将root设置为每次时都指向新节点。我不认为这就是你想要的。
• 如果您尝试处理树为空的特殊情况，那么您只需检查root是否为null，然后将新节点设置为该节点。
• 确实没有必要返回ptr。由于您的BST保持对root的引用，因此您始终可以参考树的根。每次插入时，先从root开始，然后递归遍历树，直到找到合适的位置插入新节点。如果你真的必须返回参考，那么你肯定不应该将root设置为该新节点！

下面是一些伪代码来帮助你：

// Recursive function that inserts a value into a BST 
function insert(node, value): 

    //Handles the case where you have no nodes in the tree, so root is null 
    if node is null: 
     node = new Node(value) 

    // If the value is lesser than the current node's value, we need to insert it 
    // somewhere in the right subtree 
    else if value < node.value: 
     if node.right is null: 
      // This node doesn't have a right child, so let's insert the new node here 
      node.right = new Node(value) 
     else: 
      // This node has a right child, so let's go further into this subtree to 
      // find the right place to insert the new node 
      insert(node.right, value) 

    // If the value is greater than the current node's value, we need to insert it 
    // somewhere in the left subtree 
    else if value > node.value: 
     if node.left is null: 
      // This node doesn't have a left child, so let's insert the new node here 
      node.left = new Node(value) 
     else: 
      // This node has a left child, so let's go further into this subtree to 
      // find the right place to insert the new node 
      insert(node.left, value) 
    else: 
     // A node with this value already exists so let's print out an erro 
     error("Node with that value already exists") 

end function