BST只保留上次插入的值并使其为根

Question

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（），我在这里调用insert（）并尝试将字符串插入到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是否为null，然后将新节点设置为null。
• 确实不需要返回PTR。由于BST维护对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