二叉树的枚举解析和算法实现原理

如果为每个节点分配了一个标签, 则标记为二叉树；如果未为节点分配任何标签, 则为未标记的二叉树。

Below two are considered same unlabeled treesoo/\/\ oooo Below two are considered different labeled treesAC/\/\ BCAB

n个节点可以有多少种不同的未标记二叉树？

For n= 1, there is only one treeoFor n= 2, there are two treesoo/\ ooFor n= 3, there are five treesooooo/\/\/\oooooo /\\/oooo

想法是考虑左右子树中节点的所有可能计数对, 并将特定对的计数相乘。最后添加所有对的结果。

For example, let T(n) be count for n nodes.T(0) = 1[There is only 1 empty tree]T(1) = 1T(2) = 2T(3) =T(0)*T(2) + T(1)*T(1) + T(2)*T(0) = 1*2 + 1*1 + 2*1 = 5T(4) =T(0)*T(3) + T(1)*T(2) + T(2)*T(1) + T(3)*T(0)=1*5 + 1*2 + 2*1 + 5*1 =14

以上模式基本上代表
第n个加泰罗尼亚语数字
。前几个加泰罗尼亚语数字是1 1 2 5 14 42 132 429 1430 4862, …

文章图片
这里,
T(i-1)表示左子树上的节点数
T(n-1)代表右子树上的节点数
第n个加泰罗尼亚语数字也可以使用直接公式进行评估。

T(n) = (2n)! / (n+1)!n!

具有n个节点的二叉搜索树(BST)的数量也与未标记的树的数量相同。原因很简单, 在BST中我们也可以将任何密钥都设为root, 如果root是按排序顺序排列的第i个密钥, 则i-1密钥可以位于一侧, 而(n-i)密钥可以位于另一侧。
n个节点可以有多少个带标记的二叉树？
要计算标记的树, 我们可以将以上计数用于未标记的树。这个想法很简单, 每个带有n个节点的未标记树都可以创建n！通过为所有节点分配标签的不同排列来生成不同的标签树。
因此,