FULL 二叉树的数量

Question

考虑二叉树，其中每个节点要么是叶子，要么恰好拥有两个子节点（左和右，我们认为它们不同）。 n 个节点上有多少棵不同的树？
例如：
- 3 个节点 -> 1 棵树，
- 4-> 0 棵树，
- 5 -> 2 棵树，
- 6 -> 0 棵树，
- 7 -> 5 棵树，
-等等...
这个序列有公式吗？我找到了所有可能的二叉树 (Catalan number) 的公式，但我正在搜索 full 树。

Answer 1

在一棵"full"树中，有奇数个节点，每隔一个节点就是一片叶子。

如果你移除所有这些叶子，你留下的二叉树可能不完整。对于任何（可能不是完整的）二叉树，只有一种方法可以在开始、结束和每对节点之间添加一片叶子，以形成完整的二叉树。

所以具有 n 个节点的二叉树和具有 2n 个 full 树之间存在 1-1 的对应关系+1 个代码。

C(n) -- 加泰罗尼亚数 -- 是具有 n 个节点的二叉树的数量，因此也是具有 2n+1 个节点的 "full" 棵树的数量。

因此，具有 n 个节点的完整二叉树的数量为 C((n-1)/2)。由于不能有半个节点，当 n 为偶数时，答案为 0。