如果为每个节点分配了一个标签, 则标记为二叉树;如果未为节点分配任何标签, 则为未标记的二叉树。
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!通过为所有节点分配标签的不同排列来生成不同的标签树。
因此,
Number of Labeled Tees = (Number of unlabeled trees) * n!= [(2n)! / (n+1)!n!]× n!
例如对于n = 3, 有5 * 3! = 5 * 6 = 30种不同的标记树
【二叉树的枚举解析和算法实现原理】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请发表评论。
推荐阅读
- 多线程中的Java线程优先级介绍和代码实例
- 神经网络|完整的动手指南,可在Google Colab GPU上训练你的神经网络模型
- 算法|使用pytorch自己构建网络模型实战
- mongodb进阶查询(投影查询、分页查询(limit和skip)以及查询sort排序)
- 超简单!mongodb文档(document)的增删改查命令行操作和图解
- mongodb数据建模分析、数据类型、增删数据库和集合操作
- mongodb环境部署(下载、安装和配置全解(Windows和Linux))
- 使用C++实现trie树(单词查找树,字典树)
- Python元组tuple使用详解