將節點插入二叉搜索樹

Question

我已經在一個二叉搜索樹實現中插入了幾天，現在我知道我的根目前正在通過使用'insert（）'來填充， （當我使用Eclipse進行調試時，我可以看到這一點）。爲什麼我的其他節點不會添加到樹中？

這裏是我的BST類：

package binarySearchTree; 

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

@SuppressWarnings("hiding") 
private class BinarySearchTreeNode<T>{ 
    public BinarySearchTreeNode left, right; 
    private T data; //LINE 8 

    private BinarySearchTreeNode (T data,BinarySearchTreeNode left, BinarySearchTreeNode right) { 
     this.left = left; 
     this.right = right; 
     this.data = data; 
    } 
} 
private BinarySearchTreeNode<T> root; 

@SuppressWarnings("unused") 
private T search(T target, BinarySearchTreeNode<T> ptr) { 
    //find target in subtree A ptr 
    if (root == null || ptr == null) { 
     return root; //target is not in tree 
    } 
    int compare = target.compareTo(ptr.data); //compareTo(ptr.data); 
    if (compare == 0) { 
     return ptr.data; //target is found 
    } 
    if (compare < 0) { 
     return search(target, ptr.left); 
    } 
    if (compare > 0) { 
     return search(target, ptr.right); 
    } 
    return target; 
} 
public T search(T target) { 
    return search(target); 
} 
public boolean isEmpty() { 
    return root == null; 
} 
/* To insert a data into a BST, 1st search for the data, 
* if the data is found = duplicate data error 
* if the data is NOT found = a null pointer 
* Make this null pointer point to a NewNode holding data 
* new values go into the BST as leaves 
* Using public boolean insert (T node) & 
* private boolean insert (T Node, BSTNode<T> ptr) as a recursive method 
*/ 
@SuppressWarnings("unchecked") 
private boolean insert(T value, BinarySearchTreeNode<T> ptr) { 
    //T data = null; 
    //insert data in a child of ptr, return false if duplicate is found 
    //Precondition: ptr must not be null 
    int compare = value.compareTo(ptr.data); //LINE 55 
    if (compare == 0) { 
     return false; 
    } 
    if (compare < 0) { 
     if (ptr.left == null) { 
      //found insertion point 
      BinarySearchTreeNode<T> node = new BinarySearchTreeNode<>(value, null, null); 
      ptr.left.data = node; //insert data in new node 
      return true; 
     } 
    } else { 
     return insert(value, ptr.left); //LINE 67 
    } 
    if (compare > 0) { 
     if (ptr.right == null) { 
      BinarySearchTreeNode<T> node = new BinarySearchTreeNode<>(value, null, null); 
      ptr.right.data = node; 
      return true; 
     } else { 
      return insert(value, ptr.right);      
     } 
    } 
    return false; 
} 
public boolean insert(T value) {  
    if (isEmpty()) {    
     root = new BinarySearchTreeNode<T>(value, null, null); 
     return true; 
    } 
    return insert(value, root); // LINE 85 
} 
} 

這裏是我的主要（），最終我想打印在控制檯我BST的值，但首先我知道他們需要被添加到樹：

package binarySearchTree; 

公共類主要{

public static void main(String[] args) { 


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

    String s = "Hello"; 
    String s1 = "World"; 
    //String s2 = "This Morning"; 

    bstStrings.insert(s); 
    bstStrings.insert(s1); //LINE 15 
    //bstStrings.insert(s2); 

    while (true){ 
     if (!bstStrings.isEmpty()){ 
      System.out.println(bstStrings + " "); 
     } 
     System.out.println(); 
     System.out.println("You should have values above this line!");break; 
    } 
} 
} 

Answer 1

你root應該是BinarySearchTree<T>而不是T
因此，您並未將值存儲在根的子樹中。
替換此：
return insert((T) value, node);
與
return insert((T) value, root);

在你的代碼替換

如下：

public boolean insert(T value) {  
    if (isEmpty()) {    
     root = new BinarySearchTreeNode((T) value, null, null); 
     return true; 
    } 
    return insert((T) value, root); // start recursion 
}  

否則你沒有一棵樹，節點沒有相互鏈接

更新：
你得到NPE是因爲你在insert中通過了第一個比較中的左邊的孩子，即null。
您不應該返回boolean而是BinarySearchTreeNode。
你的方法應該是：

@SuppressWarnings("unchecked") 
private BinarySearchTreeNode<T> insert(T value, BinarySearchTreeNode<T> ptr) { 
    if(ptr == null){ 
     ptr = new BinarySearchTreeNode<T>(value,null,null); 
     return ptr; 
    } 
    //your code next but return the `ptr` 
} 

然後在插入你應該做的：

public void insert(T value) {  

    root = insert(value, root); 
} 

Answer 2

第一插入後，創建新的節點，但不跟他們做任何事。