构建二叉树成为二叉搜索树的方式数量

Question

我们有一个包含 n 个独特元素的集合和一个有 n 个节点的未标记二叉树。有多少种方法可以使用给定的集合填充树，使其成为二叉搜索树？

- ABC

---

链表算作（退化的）二叉搜索树吗？ - Marcelo Cantos

我认为如果根节点固定，答案应该是1，但如果允许更改根节点，我感到困惑会发生什么。 - ABC

Answer 1

当程序（任何语言）中提供“树”时，意味着将提供根节点地址以进行遍历。因此，根据我的理解，由于提供了“根节点”，这意味着树结构已经建立并固定为一种类型。

所以我认为只有一种可能的方法。

- Asheesh

Answer 2

如果“无标签”意味着没有指定的根节点，那么让 G = {G[1]..G[n]} 成为原始未标记树的图集，其根节点分别为顶点 1 ... n。

然后对于每个图形 G[i]，有且只有一种方法来填充树（为什么？——考虑树根必须包含哪个值，并进行递归下降）。

一旦您能够证明这一点，答案必须是 k，即集合 G 中互不同构的图形数。

- Foo Bah

---

我认为“未标记”意味着树的结构是固定的，因此根节点是固定的。 - ABC

答案的选项包括a) 0 b) 1 c) n! d) 第n个卡特兰数。你认为哪一个是正确答案？ - ABC

那么它将是第n个卡特兰数——它计算二叉树的数量。 - Foo Bah