递归创建特定深度的二叉树

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 作为深度，它应该创建这样的树 ONLY:

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

我的代码当前创建了上面的树，但也包括像这样的树：

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

显然这些不是深度 3。我不想要这个。我只想要前者没有这些例外。

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

Answer 1

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

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

Answer 2

问题是：

random.nextBoolean()

这一行：

if (depth > 1 && random.nextBoolean())

您打算使用此语句创建不平衡的树，但这也很有可能创建没有任何最大深度分支的树。您所需要的只是 false 在递归的早期连续返回几次，并且您得到了不想要的结果。鉴于这种情况发生的可能性为 50%，它发生的次数将超出您的想象！要保证至少一个具有最大深度的分支，您需要多一点处理。

一个建议可能是 pre-determine 树中的一个或多个分支将达到最大深度，而让其他分支碰碰运气。当你使用二叉树时，这可以用布尔值来完成：

int depth = 3;
boolean[] branch = new boolean[depth];
for (int i = 0; i < branch.length; i++) {
  branch[i] = random.nextBoolean();
}

完成后，像现在一样生成树。完成后，按照 boolean[] 的指示在树中移动，对左使用 true，对右使用 false。如果您发现特定布尔值缺少 child，并且您没有达到最大深度，请创建 child 并继续。这不是一种特别有吸引力的方法，但它既便宜又快速。

一旦这起作用，您就可以添加更多的复杂性——更有保证的分支，以及来自这些分支的额外分支——以充实树。随着最大深度的增加，降低结束分支的机会可能是明智的，否则您最终会得到一个长的最大深度分支和大量较小的分支。

Answer 3

如前所述，问题出在这一行：

if (depth > 1 && random.nextBoolean())

您需要做的是：

控制求值顺序：

考虑return new BT(operator, create(depth-1), create(depth-1));

左边的树总是先被评估，然后是右边的树。
让树产生树叶，如果其中一棵树达到了所需的深度：

我为此创建了一个布尔变量finished

因此，首先我们将创建一条具有所需深度的路径。然后我们将让其他路径创建树或叶。

    private boolean finished;

    public BT<E> create(int depth){
        if(depth<=0) { // One tree is at desired depth
            finished = true;
            return new BT<E>(null);
        }
        if(finished) // Let the other trees set a Leaf.
            if(random.nextBoolean())
                return new BT<E>(null);

        BT<E> temp = create(depth-1); // Control evaluation
        if (random.nextBoolean()) // evaluate left and right evenly distributed
            return new BT<E>(null, temp, create(depth-1));
        else return new BT<E>(null, create(depth-1), temp);

请注意，由于

，创建的树将更稀疏而不是密集

if(finished)
    if(random.nextBoolean())
        return new BT<E>(null);

您可能希望使随机变量取决于当前路径的数量。

递归创建特定深度的二叉树

Recursively Create Binary Tree at Specific Depth

java

tree

recursion

binary-tree