0

几天来，我一直在研究二叉搜索树的实现，现在我知道我的根是通过使用我的“插入（）”来填充的（我在调试时可以看到这一点，使用 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;

公共类主要{

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

2 回答 2

2

你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在第一个比较中传入了 root 的左孩子，即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); 
}
于 2013-03-12T18:05:37.463 回答
0

第一次插入后，您创建新节点，但不对它们做任何事情。

于 2013-03-12T18:06:35.747 回答