创建固定大小的二叉树

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个 child )，请原谅我没有提到这一点之前，至于我在评论中提到的堆栈，与问题无关，只是迭代遍历树的常规方式。

Answer 1

如果递归定义，树由三个元素组成:

• 一个根节点
• 左子树，它本身就是一棵树
• 右子树，它本身就是一棵树

所有这些都可以是NULL。

现在我们可以按以下方式将范围 [a, b] 中的数字分布到一棵树中:

• 根包含 (a + b)/2
• 左子树由范围 [a, (a + b)/2 - 1] 递归构建
• 右子树由范围 [(a + b)/2 + 1, b] 递归构建

起点高于终点的范围可能被认为是空的，并导致节点为 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 成立。这两个参数表示树应该持有的范围(包括两者)。