二叉树的计数

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

null

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(n)=sum_{i=1}^{n}T(i-1)T(n-i)=sum_{i=0}^{n-1}T(i)T(n-i-1)=C_n    在这里 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棵不同的树

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

© 版权声明
THE END
喜欢就支持一下吧
点赞14 分享