二叉搜索树递归插入不显示任何内容 [英] Binary Search Tree Recursive insert not displaying anything

问题描述

我在二叉搜索树上做一个小的 Java 工作，但是当我在树中实现一个节点的递归插入并显示它时，我什么也没得到.我已经研究了一段时间了，我不确定，但我认为这是一个通过引用的问题.

I'm doing a small Java work on Binary Search Tree but when I'm implementing the recursive insert of a node into the tree and display it, I don't get anything. I've been on it for a while now, I don't know for sure but I think it's a pass-by-reference problem.

这是我的代码:

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，其中 root 是要插入的节点，elem 是一个字符串，但它没有打印出任何内容，就好像根本没有填充树一样.我确定我的递归插入有问题，但我不确定在哪里，我需要使用递归插入方法，它不返回任何我认为不可能的东西.

I executed a series of insertR with the root being the node to insert into and the elem is a string but it doesn't print anything out, as if the tree was not filled in at all. I'm sure it's problem with my recursive insert but I'm not sure where, I need to use a recursive insert method that returns nothing which I think is impossible.

任何帮助都会很棒.

推荐答案

BSTNodes 的左右元素为空.您需要在插入之前创建它们.否则，他们会创建一个空的悬挂 BSTNode() 并将其插入，而不连接到树的其余部分.

Your left, right element of the BSTNodes are null. You need to create them before inserting into it. Otherwise they create an empty hanging BSTNode() and insert it, without connecting to the rest of the tree.

你可以换行，

            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 );
    }

这篇关于二叉搜索树递归插入不显示任何内容的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！