Java通过递归传递值

Question

以下是使用java的二进制搜索树的简单实现.但是,代码总是输出"BST空!!" 尽管插入元素.我哪里错了？我怀疑我的递归出错了.任何帮助是极大的赞赏.

public class BinarySearchTree {
    NODE root;
    BinarySearchTree(){
        root = null;
    }
    void insert(NODE nodeptr,int key){
        if(root == null){
            nodeptr = new NODE(key);
            return;
        }
        if(nodeptr == null){
            nodeptr = new NODE(key);
            return;
        }
        if(key <= nodeptr.data){
            insert(nodeptr.left,key);
        }
        else{
            insert(nodeptr.right,key);
        } 

    }

    void inorder(NODE nodeptr){
        if(nodeptr == null){
            System.out.println("BST empty!!");
            return;
        }
        inorder(nodeptr.left);
        System.out.println(nodeptr.data + " ");
        inorder(nodeptr.right);

    }
    /*driver program*/
    public static void main(String args[]){
        int[] a = {20,30,40,24,39};
        BinarySearchTree bst = new BinarySearchTree();
        for (int i: a){
            bst.insert(bst.root,i);
        }
        bst.inorder(bst.root);
    }
}

class NODE{
    int data;
    NODE left,right;
    NODE(int data){
        this.data = data;
        left = null;
        right = null;
    }
}

Answer 1

您的insert方法永远不会为根分配值,因此它保持为null.

如果我理解您的代码,您的插入应如下所示:

void insert(NODE nodeptr,int key){
    if(root == null){
        root = new NODE(key);
        return;
    }
    if(nodeptr == null){
        insert (root, key);
        return;
    }
    if(key <= nodeptr.data){
        if (nodeptr.left != null)
            insert(nodeptr.left,key);
        else
            nodeptr.left = new NODE(key);
    }
    else{
        if (nodeptr.right != null)
            insert(nodeptr.right,key);
        else
            nodeptr.right = new NODE(key);
    } 

}

• 如果root为null,则忽略传递nodeptr并放在key树的根处.
• 如果nodeptr为null,请尝试从树的根开始插入新密钥.
• 否则,一旦你找到一个null nodeptr.left或者nodeptr.right,你必须将新的放在key那里,因为如果你进行另一个递归调用,你将传递一个空节点,并且递归将永远不会结束.