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

2021年3月12日13:17:32 发表评论 410 次浏览

``````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``````

。前几个加泰罗尼亚语数字是1 1 2 5 14 42 132 429 1430 4862, …

T(i-1)表示左子树上的节点数

T(n-1)代表右子树上的节点数

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

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

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