algorithm - 标记与未标记二叉树？

Question

这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:对引号中的问题提供一些帮助也非常好:)

Answer 1

二叉树可以为每个节点分配标签，也可以不分配标签。对于给定的具有 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

希望这有助于理解差异。