Вставить узел в двоичное дерево поиска

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

А вот мой Main(), в конце концов, я хотел бы напечатать значения моего BST в консоли, но сначала я знаю, что они должны быть добавлены к дерево:

package binarySearchTree; 

общественного класса Main {

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

После первого включения, вы создаете новые узлы, но ничего не делать с ними.