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

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

Below two are considered same unlabeled trees
    o                 o
  /   \             /   \ 
 o     o           o     o 

Below two are considered different labeled trees
    A                C
  /   \             /  \ 
 B     C           A    B

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

For n  = 1, there is only one tree
   o

For n  = 2, there are two trees
   o      o
  /        \  
 o          o

For 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) = 1
T(2) = 2

T(3) =  T(0)*T(2) + T(1)*T(1) + T(2)*T(0) = 1*2 + 1*1 + 2*1 = 5

T(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！通过为所有节点分配标签的不同排列来生成不同的标签树。

因此,

Number of Labeled Tees = (Number of unlabeled trees) * n!
                       = [(2n)! / (n+1)!n!]  × n!

例如对于n = 3, 有5 * 3！ = 5 * 6 = 30种不同的标记树

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