binary-tree - FULL 二叉树的数量

Question

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

Answer 1

在“完整”树中，有奇数个节点，每隔一个节点就是一片叶子。

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

因此，具有 n 个节点的二叉树与具有 2n+1 个代码的完整树之间存在 1-1 的对应关系。

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

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