java - 在特定深度递归创建二叉树

Question

我想创建一个具有特定深度的二叉树。 到目前为止，我的代码创建了二叉树直到特定的最大深度，但也创建了具有较低最大深度的树。我将在下面说明我的问题。

到目前为止我的代码(方法称为create):

public class BT<E>{
   E value;
   BT<E> left, right;

   public BT(E value)
   {
      this.value=value;
   }   

   public BT (E value, BT left, BT right) 
   {
      this.value = value;
      this.left = left;
      this.right = right;
   }

   private static final String[] random = {"a","b","c","d"};
   public static BT create(int depth) {
      if (depth > 1 && random.nextBoolean())//if not at the maximum depth
      //choose randomly a,b,c,d - nextBoolean ensures it is not balanced all the time
      {
         String random = OPERATORS[random.nextInt(OPERATORS.length)];
         return new BT(operator, create(depth-1), create(depth-1));//recursively create tree
      } 
      else {//when node is a leaf node, make it X
         String t = "x";
         return new BT(t);
      }
   }
}

问题: 如果我输入 3 作为深度，它应该创建这样的树仅:

    (c)              (d)         (a)
 (b)   (a)         (b)        (d)   (c)
(x)(x)(x)(x)     (x)  (x)             (x)

我的代码当前创建如上所述的树，但还包括如下树:

(x)       (c)           (d)
             (x)      (x) (x)

显然这些不具有深度 3。我不想要这个。我只想要前者，没有这些异常(exception)。

有人可以看一下我的代码并告诉我我做错了什么以及如何纠正它。

Answer 1

最简单的方法是创建一个调用您的创建树函数的包装函数。

该函数将使用您的函数创建一个随机空闲，测试它是否具有所需的深度 X 长度。如果是，它将返回；如果没有，它将再次调用您的函数，直到找到具有正确深度的树