枚举搜索树

Question

根据这个问题，特定大小的不同搜索树数量等于一个卡特兰数。是否可以枚举这些树呢？也就是说，有人能否实现以下两个函数：

Node* id2tree(int id); // return root of tree

int  tree2id(Node* root); // return id of tree

我问这个问题是因为树的二进制代码（参见此问题的一个答案）将是一种非常有效的代码，用于表示范围未知的任意大的整数，即，可变长度编码的整数。

0 -> 0
1 -> 100
2 -> 11000
3 -> 10100
4 -> 1110000
5 -> 1101000
6 -> 1100100
7 -> 1011000
8 -> 1010100
etc

请注意，每个编码长度的整数数量为1、1、2、5、...(即卡特兰数列)。

- ragnarius

Answer 1

应该可以将id转换为树形结构，然后再转回去。

id和位串如下：

0 -> 0 
1 -> 100 
2 -> 11000 
3 -> 10100 
4 -> 1110000 
5 -> 1101000 
6 -> 1100100 
7 -> 1011000 
8 -> 1010100 

首先考虑到，对于一个二进制字符串，我们可以很容易地通过递归方法转换成树形结构，反之亦然（按照先序遍历，父节点输出1，叶子节点输出0）。

主要的难点在于如何将id映射到二进制字符串，以及反向映射。

假设我们按以下方式列出n个节点的所有树：

Left sub-tree n-1 nodes, Right sub-tree 0 nodes. (Cn-1*C0 of them)
Left sub-tree n-2 nodes, Right sub-tree 1 node.  (Cn-2*C1 of them)
Left sub-tree n-3 nodes, right sub-tree 2 nodes. (Cn-3*C2 of them)
...
...
Left sub-tree 0 nodes, Right sub-tree n-1 nodes. (C0*Cn-1 of them)

Cr = rth catalan number.

您提供的枚举似乎来自以下过程：我们固定左子树，枚举右子树。然后移动到下一个左子树，枚举右子树，以此类推。我们从最大尺寸的左子树开始，然后是最大尺寸-1，依此类推。

因此，假设我们有一个id = S。我们首先找到一个n，使得：

C0 + C1 + C2 + ... + Cn < S <= C0+C1+ C2 + ... +Cn+1

然后S将对应于具有n + 1个节点的树。

现在我们考虑P = S - (C0+C1+C2+ ...+Cn)，它是n + 1个节点的树的枚举位置。

现在我们找出一个r，使得Cn*C0 + Cn-1*C1 + .. + Cn-rCr < P <= CnC0 + Cn-1C1 + .. + Cn-r+1Cr-1

这告诉我们左子树和右子树各有多少个节点。

考虑P - CnC0 + Cn-1C1 + .. + Cn-rCr，我们现在可以确定左子树枚举位置（仅考虑该大小的树）和右子树枚举位置，并递归形成位串。

将位串映射到ID应该很相似，因为我们知道左子树和右子树的样子，我们所需要做的就是找到相应的位置并进行一些算术运算以获取ID。

不确定它有多大帮助。您将始终使用一些非常巨大的数字。

- Aryabhatta

Answer 2

对于非搜索二叉树，我可以理解如何实现，因为在构建树时，每个节点有三种选择（孩子的数量），受到总共达到元素N的限制。您可以找到一种方法将这样的树表示为选择序列（通过按特定顺序构建树），并将该序列表示为基数为3的数字（或者也许一个可变基数更合适）。

但是对于二叉搜索树，不是所有的元素组织方式都是可接受的。您必须遵守数值排序约束。另一方面，由于插入二叉搜索树是定义良好的，因此您可以通过具有特定插入顺序的N个数字列表来表示整个N元素的树。通过重新排列数字以按不同顺序排列，您可以生成不同的树。

当然，可以使用可变基数数字很容易地计算排列方式：第一项有N种选择，第二项有N-1种选择，等等。这给出了一个由N个数字组成的序列，您可以将其编码为基数从N到1不断变化的数字。从可变基数到二进制或十进制的编码和解码，只需要对标准固定基数转换算法进行微小调整，便可以轻松完成（使用模运算和除法操作）。

因此，您可以将数字转换为排列，并且在给定数字列表的情况下，您可以将排列（该列表的排列）从二叉搜索树转换为二叉搜索树。现在我认为您可以通过对整数1到N进行排列来获取大小为N的所有可能的二叉搜索树，但我不是完全确定，而试图证明这一点有点过于复杂了。

我希望这是一个讨论的好起点。

- Joren

---

Catalan数以O(4^n)的速度增长，比阶乘要慢。 - A. Rex

你说得对。我不记得为什么认为它们生长更快了，但我已经删除了错误。谢谢。 - Joren