首页 文章

用Java递归创建二进制搜索树

提问于
浏览
0

我一直在尝试创建一个递归方法,它将创建一个完整的二叉搜索树 . 此方法返回对此树的根的引用 . 作为参数,我传递树的深度以及存储在当前子树的根中的数字 . 我已经设法为2个基本情况设计解决方案,当深度为0和1时,但是当我尝试使用大于1的数字时,我只得到0级和1级实例化而不是下一个 . 任何帮助都会很棒

public class BinaryNode {
private int data;
private BinaryNode left, right;

public BinaryNode(int initialData, BinaryNode initialLeft,
        BinaryNode initialRight) {
    data = initialData;
    left = initialLeft;
    right = initialRight;
}
   public static BinaryNode BSTFactory(int top,int depth) {
    BinaryNode root=new BinaryNode(top,null,null);
    BinaryNode leftChild,rightChild;
    if(depth==0)
        //return root;
    if(depth==1){
        //create 2 children left and right
        leftChild=new BinaryNode(top-1,null,null);
        rightChild=new BinaryNode(top+1,null,null);
        root=new BinaryNode(top,leftChild,rightChild);
        //return root;
    }
    if(depth>1){

        leftChild=BSTFactory(top-1,depth-1);
        rightChild=BSTFactory(top+1,depth-1);
        root=new BinaryNode(top,leftChild,rightChild);
        //return root;
    }
    return root;
}
   public class Applications {

public static void main(String[] args){
    BinaryNode root2=BinaryNode.BSTFactory(8, 2);
System.out.println(root2.toString());


   }

}

This is the output:
  data: 8
  8's left: data: 7
  7's left: null
  7's right: null
  8's right: data: 9
  9's left: null
  9's right: null

1 回答

  • 1

    当空树由 null 表示时,通常不需要多个基本情况 .

    public class BinaryNode {
        public static BinaryNode bstFactory( int data, int depth ) {
            if ( depth >= 31 )
                throw new IllegalArgumentException( "too deep for integer data" );
            else if ( depth < 0 )
                throw new IllegalArgumentException( "non-sensical depth" );
            return ( depth == 0 )
                ? null
                : new BinaryNode(
                    data,
                    bstFactory( data - ( 1 << depth ), depth - 1 ),
                    bstFactory( data + ( 1 << depth ), depth - 1 )
                );
        }
        BinaryNode( int data, BinaryNode left, BinaryNode right ) { /*...*/ }
    }
    

相关问题