2

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

任何帮助都会很棒。

4

3 回答 3

2

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 );
    }
于 2012-12-06T04:24:35.410 回答
1

尽管递归插入 BST 似乎微不足道，但很容易犯下参数传递错误，从而使您的尝试无效。要递归调用插入函数，您必须将对象BSTNode root作为参数之一传递并更改其内容而不是其指向的内容。

在下面的代码中，root = new BSTNode( elem );只改变了局部变量root所指向的地址，而改变对 . 来说是不可见的this.root。在赋值之前，root有一个值，它是从BST 为空时null复制的值。this.root分配后，root指向一些新创建BSTNode的数据来自elem. 代码的意图是this.root指向同一个 new BSTNode，但是没有办法通过将本地root指向它来实现这一点。insertR返回时，仍然this.root指向null!!

insertR(root.left, elem);和 也发生同样的错误insertR(root.right, elem);。传递了参数，但由于没有进行内容更改，因此函数调用只会返回，没有更新到 BST 的信息。

public void insert(Comparable elem) {
    insertR(this.root, elem);
}

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

}

要递归地更改 BST，应针对对象包含的变量而不是对象变量指向的变量进行更改。因此 when this.rootis null，您应该在其他地方而不是 inside 处理第一次插入insertR，如下所示：

public void insert(Comparable elem) {
    if (this.root == null) {
        this.root = new BSTNode(elem);
    } else {
        insertR(this.root, elem);
    }
}

Arcturus 的附加插入代码是正确的，因为对 的内容所做的更改root立即传播到this.root，因为它们指向同一个BSTNode对象。当然这里root要求不是，因为上面的代码已经处理了大小写null，所以满足了。null

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 );
}
于 2013-07-27T06:00:28.033 回答
0

这将设置 BST 根并允许类正常工作，更改

    if ( root == null ) {
        root = new BSTNode( elem );
    }

到

    if ( root == null ) {
        root = new BSTNode( elem );
        if ( root.element != null ) {
            this.root = root;
        }
    }
于 2012-12-06T05:33:03.697 回答