据this问题中的不同的搜索树具有一定规模的的数量等于加泰罗尼亚数。是否有可能的枚举的那些树？也就是说，有人可以实现以下两个功能：

According to this question the number of different search trees of a certain size is equal to a catalan number. Is it possible to enumerate those trees? That is, can someone implement the following two functions:

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

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

（我问，因为二元$ C $下的树（SE的答案之一this问题）将是一个非常有效的code为未知的范围内，也就是说，一个的可变长度code整数的

(I ask because the binary code for the tree (se one of the answers to this question) would be a very efficient code for representing arbitrarily large integers of unknown range, i.e, a variable length code for integers

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

请注意，每个code长整数的个数为1，1，2，5，......（加泰罗尼亚序列）。 ）

notice that the number of integers of each code length is 1, 1, 2, 5,.. (the catalan sequence). )

推荐答案

这应该是可能的ID转换成树和背部。

It should be possible to convert the id to tree and back.

ID和位串之中：

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

首先考虑给定一个位串的事实，我们可以轻松地移动到树（递归方法），反之亦然（preorder，输出1为家长和0叶）。

First consider the fact that given a bitstring, we can easily move to the tree (a recursive method) and viceversa (preorder, outputting 1 for parent and 0 for leaf).

主要的挑战来自于试图将ID映射到比特串，反之亦然。

The main challenge comes from trying to map the id to the bitstring and vice versa.

假设我们列出了n个节点的树如下：

Suppose we listed out the trees of n nodes as follows:

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等。

The enumeration you have given seems to come from the following procedure: we keep the left subtree fixed, enumerate through the right subtrees. Then move onto the next left subtree, enumerate through the right subtrees, and so on. We start with the maximum size left subtree, then next one is max size -1, etc.

所以说我们有一个id = S说。我们先找到一个N使得

So say we have an id = S say. We first find an n such that

C0 + C1 + C2 + ...的C n＆其中; S＆LT; = C0 + C1 + C2 + ... +道道通+ 1

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

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

Then S would correspond to a tree with n+1 nodes.

所以，你现在考虑P = S - （C0 + C1 + C2 + ... +道道通），这是在N + 1个节点的树的枚举的位置

So you now consider P = S - (C0+C1+C2+ ...+Cn), which is the position in the enumeration of the trees of n+1 nodes.

现在我们找出的R，使得道道* C0 +道道通-1 * C1 + ... +道道通-R *为CR P＆LT; = CN * C0 +道道通-1 * C1 + ... +道道通-R + 1 *的Cr-1

Now we figure out an r such that Cn*C0 + Cn-1*C1 + .. + Cn-r*Cr < P <= Cn*C0 + Cn-1*C1 + .. + Cn-r+1*Cr-1

这告诉我们有多少结点的左子树和右子树有。

This tell us how many nodes the left subtree and the right subtree have.

考虑P - 简体* C0 +道道通-1 * C1 + ... +道道通-R *铬，现在我们可以计算出确切的左子树枚举的位置（即大小只考虑树）以及确切的右子树枚举位置和递归形式的比特串。

Considering P - Cn*C0 + Cn-1*C1 + .. + Cn-r*Cr , we can now figure out the exact left subtree enumeration position(only considering trees of that size) and the exact right subtree enumeration position and recursively form the bitstring.

映射位串到的ID应该是相似的，因为我们知道左子树和右子树的样子，所有我们需要做的是找到相应​​的位置，并做一些运算，以获得ID。

Mapping the bitstring to the id should be similar, as we know what the left subtree and right subtrees look like, all we would need to do is find the corresponding positions and do some arithmetic to get the ID.

不知道它是多么的有帮助的，但。你会用一些pretty的巨大的数字所有的时间来工作。

Not sure how helpful it is though. You will be working with some pretty huge numbers all the time.