这Wolfram链接谈到了一些关于“标记”二叉树的内容。那么也有一种叫做“未标记”二叉树的东西吗?对两者的简明解释会非常好。
我为什么要搜索这个?
我正在尝试回答这个问题:
We are given a set of n distinct elements and an unlabeled binary tree with n nodes. In how many ways can we populate the tree with the given set so that it becomes a binary search tree?
现在,我知道给定 n 个节点的二叉树的数量是第 n 个 Catalan number , 但现在我很困惑:那么这个公式适用于上述两种类型中的哪一种?
PS:对引号中的问题提供一些帮助也非常好:)
最佳答案
二叉树可以为每个节点分配标签,也可以不分配标签。对于给定的具有 n 个节点的未标记二叉树,我们有 n!分配标签的方法。 (考虑节点的有序遍历,我们希望将其映射到标签 1..n 的排列)
从上面我们可以看出,第n个加泰罗尼亚数给出了未标记二叉树的数量。
以 n = 3 为例,我们有以下树 5 棵树:
1. o 2. o 3. o 4. o 5. o
\ \ / \ / /
o o o o o o
/ \ / \
o o o o
一般来说,这个数字是由 N-th Catalan Number. 的公式给出的
要获得标记树的数量,您必须乘以 n!所以对于 n = 3,我们总共有 30 棵树。基本上,我们为上面的五个未标记 BST 中的每一个创建了 !3 = 6 个带有标签的标记 BST:
1: 1, 2, 3
2: 1, 3, 2
3: 2, 1, 3
4: 2, 3, 1
5: 3, 1, 2
6: 3, 2, 1
希望这有助于理解差异。
关于algorithm - 标记与未标记二叉树?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29668827/