满二叉树的递归关系

Question

对于一般的n，推导Bn的递推关系。这里Bn表示具有n个顶点的满二叉树的数量。我发现它是 B(n)=2B(n-1) +1。但解完这个方程后，最终的答案是O(2ⁿ)。但最终的答案应该是

B_n = ⁿ⁻²Σ_i=1 (B_iB_n−i−1)

()

如何导出完整二叉树的递归关系，以便我的最终答案应该是这样？

Answer 1

首先请注意，非空满二叉树始终具有奇数个节点。例如，不存在具有两个节点的完整二叉树。因此，仅用 𝐵_𝑛−1 来表示 𝐵_𝑛 的公式不可能是正确的。假设 𝐵₁ 是 1（只是一个根节点），您的 B(n)=2B(n-1) +1 想法意味着 𝐵₂ 是 3，但这是不正确的； 𝐵₂ 是 0。即使我们计算有 2 个非满二叉树节点的二叉树，我们也永远不会达到 3。

我们可以构造一个递归关系如下：

给定一个根节点，则该根节点要么没有子节点（当 𝑛 = 1 时），要么有 两个 子节点，每个子节点都是一个完整二叉树的根。给定 𝑛 > 1，这两个子树将至少有 1 个节点，最多 𝑛−2 个节点（以允许右子树至少有 1 个节点）：如果左子树有 𝑖 个节点，则右子树有𝑛−1−𝑖 节点（从计数中减去根）。如果我们计算给定 𝑖 值的子树的所有可能形状，并计算 𝑖 的所有可能值的所有可能形状，那么我们就得出 𝑛 的形状总数。

这导致了您引用的递归关系，但它需要用两个基本案例来完成才能有意义：

• 𝐵₁ = 1
• 𝐵₂ = 0
• 𝐵_𝑛 = ^𝑛−2Σ_𝑖=1 (𝐵_𝑖𝐵_{𝑛−𝑖−1})

请注意，当 𝑛 为偶数时，递归表达式将始终为 0，因为在每一项中，𝑖 或 𝑛−𝑖−1 都是偶数，这根据 𝐵₂ 的基本情况意味着所有涉及的乘积都有 0因子，导致总和为 0。