FULL 二叉树的数量

Question

考虑二叉树，其中每个节点要么是叶子节点，要么恰好拥有两个子节点（左右，我们认为是不同的）。n节点上有多少种不同的树？
例如：
- 3 个节点 -> 1 棵树，
- 4-> 0 棵树，
- 5 -> 2 棵树，
- 6 -> 0 棵树，
- 7 -> 5 棵树，
- 等等......
有什么公式对于这个序列？我已经找到了所有可能的二叉树（加泰罗尼亚数）的公式，但我正在寻找完整的树。

Answer 1

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

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

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

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

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