二进制搜索树递归插入不显示任何内容

Question

我在Binary Search
Tree上做了一个小型的Java工作，但是当我实现将节点的递归插入树中并显示它时，我什么也没得到。我已经花了一段时间了，我不确定，但是我认为这是通过引用的问题。

这是我的代码：

public class BST {

    private BSTNode root;

    public BST() {
        root = null;
    }

    public BSTNode getRoot() {
        return root;
    }

    public void insertR( BSTNode root, Comparable elem ) {

        if ( root == null ) {
            root = new BSTNode( elem );
        }
        else {
            if ( elem.compareTo( root.element ) < 0 ) {
                insertR( root.left, elem );
            } else {
                insertR( root.right, elem );
            }
        }

    }

    public void printInOrder (BSTNode root) {
        if (root != null) {

            printInOrder(root.left);
            System.out.println(root.element);
            printInOrder(root.right);

        }
    }
}

class BSTNode {

    protected Comparable element;
    protected BSTNode left;
    protected BSTNode right;

    protected BSTNode ( Comparable elem ) {

        element = elem;
        left = null;
        right = null;

    }

}

我执行了一系列insertR，其根是要插入的节点，而elem是一个字符串，但是它不会打印出任何内容，就好像根本没有填充树一样。我确定我的递归插入有问题，但是我不确定在哪里，我需要使用递归插入方法，该方法不会返回任何我认为不可能的东西。

任何帮助都会很棒。

Answer 1

BSTNodes的左右元素为空。您需要先创建它们，然后再插入其中。否则，它们将创建一个空的悬挂BSTNode（）并将其插入，而不连接到树的其余部分。

您可以更改线，

            if ( elem.compareTo( root.element ) < 0 ) {
                insertR( root.left, elem );
            } else {
                insertR( root.right, elem );
            }

至

 if ( elem.compareTo( root.element ) < 0 ) {
        if ( root.left == null )
             root.left = new BSTNode( elem );
        else
            insertR( root.left, elem );
    } else {
        if ( root.right == null )
             root.right = new BSTNode( elem );
        else
             insertR( root.right, elem );
    }