問題描述

我在二叉搜索樹上做一個(gè)小的 Java 工作，但是當(dāng)我在樹中實(shí)現(xiàn)一個(gè)節(jié)點(diǎn)的遞歸插入并顯示它時(shí)，我什么也沒得到.我已經(jīng)研究了一段時(shí)間了，我不確定，但我認(rèn)為這是一個(gè)通過引用的問題.

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;

    }

}

我執(zhí)行了一系列 insertR，其中 root 是要插入的節(jié)點(diǎn)，elem 是一個(gè)字符串，但它沒有打印出任何內(nèi)容，就好像根本沒有填充樹一樣.我確定我的遞歸插入有問題，但我不確定在哪里，我需要使用遞歸插入方法，它不返回任何我認(rèn)為不可能的東西.

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.

任何幫助都會(huì)很棒.

推薦答案

BSTNodes 的左右元素為空.您需要在插入之前創(chuàng)建它們.否則，他們會(huì)創(chuàng)建一個(gè)空的懸掛 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 );
    }

這篇關(guān)于二叉搜索樹遞歸插入不顯示任何內(nèi)容的文章就介紹到這了，希望我們推薦的答案對(duì)大家有所幫助，也希望大家多多支持html5模板網(wǎng)！