二叉搜索树递归不起作用

Question

我创建了这个二进制搜索树。我使用循环和递归以2种形式编写了insert方法。递归代码虽然看似正确，但无法正常工作，我无法弄清楚问题出在哪里。当我使用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;
}

先前代码的问题是，您仅返回了最后插入的节点的值。这就是为什么您总是将左右节点为空的原因。