二叉查找树递归不起作用

Question

我创造了这个二叉查找树。我使用循环和递归编写了两种形式的插入方法。递归代码虽然看起来是正确的，但并不工作，我想不出问题是什么。当我使用insertRecursion方法创建树时，leftChild和rightChild总是为null。

public class BinarySearchTree {
private class Node{
    private int value;
    private Node leftChild;
    private Node rightChild;
    public Node(int value){
        this.value=value;
    }
    public String toString(){
        return ""+this.value;
    }
}
private Node root;
public BinarySearchTree(int value){
    root=new Node(value);
}
public void insertRecursion(int value){
    Node current=root;
    insertRecursionForm(current,value);
}
private Node insertRecursionForm(Node root, int value){
    if(root==null){
        root=new Node(value);
        return root;
    }
    if(value<root.value){
        return insertRecursionForm(root.leftChild,value);
    }else{
        return insertRecursionForm(root.rightChild,value);
    }
}

public void insert(int value){
    Node current=root;
    while(true) {
        if (value < current.value) {
            if (current.leftChild == null) {
                current.leftChild= new Node(value);
                break;
            }else{
                current=current.leftChild;
            }
        }else if(value>current.value) {
            if (current.rightChild == null) {
                current.rightChild= new Node(value);
                break;
            }else{
                current=current.rightChild;
            }
        }
    }
}

}

Answer 1

像这样试试：

private Node insertRecursionForm(Node root, int value){
    if(root==null){
        root=new Node(value);
        return root;
    }
    if(value<root.value)
    {
        root.leftChild = insertRecursionForm(root.leftChild,value);
    }else
    {
        root.rightChild = insertRecursionForm(root.rightChild,value);
    }
    return root;
}

您之前代码的问题是，您只返回了最后插入的节点的值。这就是为什么你总是有左，右节点为空。