创建固定大小的二叉树

Question

我正在尝试创建一个二叉树。我只给出了树中节点的数量。第一件事就是使用索引（BFS订单）来跟踪总节点数，然后使用递归定义。这是我的伪代码来做到这一点。

N = 10   //binary tree total node count 
i = 0   //global integer 
function() 
    if i > N 
     return True 

    create node i 
    i = i + 1 
    function(i) //left 
    i = i + 1 
    function(i) //right 

我必须在这个定义中使用一个全局变量，这让我觉得我可能违反了递归规则。有没有更好的方式去做我所做的事情，如果是这样，是否可以改进？

注：我在询问理论方法，而不是代码。

编辑：我刚刚意识到这种方法失败。我很乐意提供建议。

澄清：这棵树的要求是不添加元素的深度，如果前面的深度不填充节点（所有节点有2个孩子），原谅我之前没有提到这一点，作为我在评论中提到的堆栈，它与问题无关，只是迭代地遍历树的常规方式。

Answer 1

树包括三个要素，如果定义递归：

• 根节点
• 一个左子树，其是树本身
• 一个右子树，其是树本身

所有这些可能是NULL。

现在，我们可以在一个范围内[a, b]分配数成树以下列方式：

• 根含(a + b)/2
• 左子树是建立在递归
• 右子树是建立在一系列[a, (a + b)/2 - 1]范围[(a + b)/2 + 1, b]递归地

起始点高于结束点的范围可能是consi被认为是空的并且导致节点为NULL。这种分配确保左右子树的大小最多相差1个，并且在另一个级别填满之前，每个级别都完全填满。

例如为：

N = 6 
            [0, 5] 

       [0, 1]    2     [3, 5] 

     [0]  1  []    [3]   4   [5] 

[]  0  []      []  3  []  [] 5 [] 

此外，该算法生成一个BST（实际上这基本上是一个二分搜索的“反向”）。现在的算法本身：

function(a, b): 
    if b < a: return NULL 

    n = create node (a + b)/2 
    n.left = function(a, (a + b)/2 - 1) 
    n.right = function((a + b)/2 + 1, b) 

    return n 

树可以通过调用生成：

function(1, N) 

或者任何其它参数a和b应该工作，其中a + N - 1 = b成立。这两个参数表示应该由树保持的范围（包括两端）。