通過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。