通过Java方法递归生成一个完整的二叉树

Question

该方法假定需要两个参数一个用于深度，另一个用于树的根的整数值。例如：对于任何给定的N，返回深度为N的完整二分搜索树的根引用，使得节点存储整数1,2，...，2 N + 1 - 1。我努力做到这一点。这里是我的：

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

      leftChild=BSTFactory(top-1,depth-1); 
      rightChild=BSTFactory(top+1,depth-1); 
      root=new BinaryNode(rightChild,leftChild,top); 
      return root; 
     } 
     return root; 
    } 

Answer 1

首先，你的方法的两个参数相互依赖。例如，BSTFactory（1,3）不能是最小节点为1的完整二叉树，因为如果根已包含最小节点，则左子树必须为空（除非在您的系统中允许使用负值树，从你的问题中不清楚，因为你似乎希望树存储从1开始的整数）。

因此，我会建议一个只接受深度的包装方法，并计算匹配的根节点。我们将看到这两个参数以后如何相关。

现在让我们来看看一些小的满二叉树找出递归：

深度0

1 

深度1

2 
1  3 

深度2

 4 
    2 6 
1 3 5 7 

深度3

  8 
    4  12 
    2  6 10 14 
1 3 5 7 9 11 13 15 

我们能从这些例子中学到什么？

如果我们正在创造深度为n的全二叉搜索树：

1. 根将2^n
2. 左子树将在root - 2^(n-1)
3. 右子树将根植在root + 2^(n-1)

因此扎根，在recusion应该是：

public static BinaryNode BSTFactory(int root, int depth) 
{ 
    BinaryNode leftChild,rightChild; 
    if (depth==0){ 
     return new BinaryNode(null,null,root); 
    } else { 
     leftChild=BSTFactory(root-Math.pow(2,depth-1),depth-1); 
     rightChild=BSTFactory(root+Math.pow(2,depth-1),depth-1); 
     return new BinaryNode(rightChild,leftChild,root); 
    } 
} 

请注意，为了这个工作（即，你最小的节点将是1），你必须调用具有root = 2^depth深度的根和深度的方法。为保证，让我们定义一个包装方法：如果你调用任意根和深度两个参数法

public static BinaryNode BSTFactory(int depth) 
{ 
    return BSTFactory (Math.pow(2^depth),depth); 
} 

，你可以得到二叉树如：

BSTFactory（6,1）

 6 
    5 7 

BSTFactory（1,2）

 1 
    -1 3 
    -2 0 2 4 

还有满二叉树，但最小值不是1。