将节点插入二叉查找树

Question

几天来，我一直在使用二进制搜索树实现，我已经到了知道我的根正在通过使用我的“插入（）”来填充的地步（当我使用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

第一次插入后，创建新节点，但不使用它们。

Answer 2

你的根应该是二进制搜索树

在代码中，替换如下：

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

否则，就没有树，节点也不会相互链接

更新：
您获得NPE，因为您在第一次比较中传递了插入根的左子级，即空
不应返回布尔值，而应返回二进制搜索树节点
你的方法应该是：

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

然后在insert中，您应该执行以下操作：

public void insert(T value) {     

    root = insert(value, root); 
}