binary-tree - 使用加泰罗尼亚数概念的 N 个节点可能有多少二叉树

Question

所以我正在理解加泰罗尼亚数字概念并尝试使用topDown DP方法在代码中实现它，所以递归关系来自我所学到的，

f(N) signifies total count of binary search trees possible by N number of nodes

f(N) = f(i-1).f(N-i)

where, 
i = 1.....N (i signifies root node and traverse through all the nodes),
N is total number of nodes present in the binary tree,
f(i-1) signifies number of left subtrees possible when i is a root node,
f(N-i) signifies number of right subtrees possible when i is a root node.

有一个数学公式，我们可以通过它找到 f(N) 值，

2NcN/(N+1)

. 并且，N 个节点可能的二叉树总数，

(N 的阶乘) * f(N)

我的疑问：

二叉树和二叉搜索树有什么区别？我觉得两者都定义了相同的含义，但是我不知道有一个区别，所以请帮助我。

标签： binary-treebinary-search-treecatalan

Answer 1

二叉树和二叉搜索树有什么区别？

这种树的形状没有区别，但是二叉搜索树对其节点具有的值施加了约束，这对于（仅）二叉树是不存在的：

• 节点的值不得小于其左子树中的任何值
• 节点的值不能大于其右子树中的任何值

表达这种约束的另一种方式是：

• 树中值的有序遍历必须是非递减的。

实际上，这意味着当您获得：

• 带节点的二叉树形状
• 树中存在的一组唯一值

...那么只有一种可能的方法将这些值与树的节点相关联，使其成为二叉搜索树。如果它不必是二叉搜索树，那么有！建立这种关联的方法。

结论：

给定，那么（第^th加泰罗尼亚数字）表示：

• 具有无值节点的二叉树的数量（即二叉树的形状数量）
• 具有不同值的二叉搜索树的数量

具有不同值的二叉树的数量是！