二叉树的计数

如果为每个节点分配了标签，则二叉树被标记；如果未为节点分配任何标签，则二叉树被取消标记。

Below two are considered same unlabelled trees    o                 o  /                /     o     o           o     o Below two are considered different labelled trees    A                C  /                /    B     C           A    B 

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

For n  = 1, there is only one tree   oFor n  = 2, there are two trees   o      o  /           o          oFor n  = 3, there are five trees    o      o           o         o      o   /                 /        /           o          o       o    o     o          o /                                      /o              o                  o      o

其思想是考虑左、右子树中节点的所有可能计数对，并乘以特定对的计数。最后，将所有对的结果相加。

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 

上述模式基本上代表了 加泰罗尼亚数字 前几个加泰罗尼亚人的数字是1 1 2 5 14 42 132 429 1430 4862，… 在这里 T（i-1）表示左子树上的节点数 T（n）−i-1）表示右子树上的节点数

n’th Catalan数也可以用直接公式计算。

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

具有n个节点的二叉搜索树（BST）的数量也与未标记树的数量相同。原因很简单，在BST中，我们也可以将任何键设为根，如果根是按排序顺序排列的第i个键，那么i-1键可以位于一侧，而（n-i）键可以位于另一侧。

有n个节点可以有多少标记的二叉树？ 要计算标记树的数量，我们可以使用上面的计数来计算未标记树的数量。这个想法很简单，每个有n个节点的未标记树都可以创建n个！通过将不同的标签排列分配给所有节点，可以获得不同的标签树。

因此

Number of Labelled Trees = (Number of unlabelled trees) * n!                       = [(2n)! / (n+1)!n!]  × n!

例如，对于n=3，有5*3！=5*6=30棵不同的树

如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论