构建独特的二叉查找树

Question

我正在处理一个算法问题。给定n，生成所有存储值为1…n的结构唯一的二叉搜索树。解决方案是枚举序列中的每个数字i，并将该数字用作根，其左侧的子序列1...(i-1)将位于根的左支上，同样，右侧子序列(i+1)…n将位于根的右支上。然后从子序列递归构建子树。这种方法确保构造的BST都是唯一的，因为它们具有唯一的根。

现在我的问题是：如果树不限于二叉搜索树，如果可以是任意二叉树，那么解决方案会是什么？我仍然想遍历所有根为i的情况，其中i = 1，...，n。左子树不必在1…(i-1)范围内，右子树也不必在(i+1)…n范围内。但是如何排列它们呢？创建(i-1)个元素的任意子集，然后应用？

- Sarah

---

将其变成二叉搜索树（或不是）并不影响树中可能存在的结构，只影响该结构节点中数据的顺序。因此，除非您以某种相当奇怪的方式定义“结构上独特”，否则节点是否按BST排序都没有区别。 - Jerry Coffin

Answer 1

假设您得到以下问题：给定n个磁盘，将它们排列成唯一的二叉树形状。然后，按照您在问题中的正确推理，您可以说以下内容：我将编号为1、2、3、...、n的磁盘；然后我将（递归地）构建根节点位于磁盘＃1、然后是磁盘＃2等的树。

因此，您（正确地）发现的根节点有向图与节点中的内容没有任何关系，更不用说内容是否满足BST不变性的问题了。鉴于您在这里的问题，

1. 如果问题是有多少个根有向图存在，则与以前相同。
2. 如果问题是有多少种根有向图+节点内容的组合，则只需像您所做的那样枚举根有向图，然后对于每个根有向图，枚举1、2、... n的排列。

如果是这种情况，并且您不需要枚举，而是近似计算这些树的数量，请注意，这是n！乘以卡特兰数。

- Ami Tavory

Answer 2

使用BST算法。这将生成树的唯一形状。这些形状是唯一的，因为对于每个根n，在左子树中有n-1个元素，其余元素在右边。

然后，对于每个形状，有n！种元素排序方式。这给出了任意树的结果。

- maniek