Java 中的 BST 实施

Question

这是我在 Java 中实现的 BST。

public class BST {
    Node root;

    public BST(){
        root = null;
    }
//    public BST(int item){
//        root = new Node(item);
//    }

    private class Node{
        int data;
        Node left;
        Node right;

        public Node(int data){
            this.data = data;
            this.left = null;
            this.right = null;
        }
    }

    public void add(int item){

        add(item, root);
    }

    private  Node add(int item, Node p ){
        if(p == null){
            p = new Node(item);
        }
        else if(item < p.data) p.left = add(item, p.left);
        else if(item > p.data) p.right = add(item, p.right);
        return p;
    }
     public void inorder(){
          inorder(root);

     }
    private void inorder(Node p){
        if(p == null) return;
        inorder(p.left);
        System.out.print(p.data + " ");
        inorder(p.right);
    }
}

这是调用代码。

public class Main {

    public static void main(String[] args) {
    // write your code here
        //BST bst = new BST(13);
        BST bst = new BST();
        bst.add(12);
        bst.add(7);
        bst.add(3);
        bst.add(2);
        bst.add(19);
        bst.add(4);
        bst.add(17);
        bst.add(11);
        bst.inorder();
    }
}

这里的问题是当我使用 BST 参数化构造函数时，一切都按预期工作。但是，如果我不使用默认构造函数，根将继续保留 null 并且不会添加任何内容。似乎无法理解为什么会这样。调试器在 add 帮助程序调用中给出了 null pointer exception。但是如果 null root 是调用者，那么我的 add 的定义方式就不应该有任何例外。我的问题是为什么带有默认构造函数的 BST 不起作用？

Answer 1

在这种方法中 private Node add(int item, Node p ) 您将返回 p 但 public void add(int item) 不会存储它。所以基本上你返回的任何对象都没有引用。

变化：

public void add(int item){

        add(item, root);
    }

至：

public void add(int item){
        if (root == null) 
            root = add(item, root);
        else 
            add(item, root);
    }

Answer 2

像这样更正 add 方法：

public void add(int item)
{
    root = add(item, root);
}

而不是这个：

public void add(int item)
{
    add(item, root);
}

Java 中的 BST 实施

BST implementation in Java

java

binary-search-tree