枚舉搜索樹

Question

根據this question不同搜索樹的數量的一定大小等於一個加泰羅尼亞數。那些樹可以列舉？也就是說，有人可以實現以下兩個功能：

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

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

（我問，因爲該樹的二進制代碼（SE答案this question之一）將是代表未知任意大的整型一個非常高效的代碼範圍，即，可變長度整數代碼

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

通知每個碼長度的整數的個數爲1，1，2，5，..（加泰羅尼亞序列）。）

Answer 1

對於一般（非搜索）二叉樹，我可以看到這將是可能的，因爲當建立樹時，每個節點都有三個選擇（孩子的數量），僅限於總數達到N的限制。可以找到一種方法來將這樣的樹表示爲一系列選擇（通過按照特定順序構建樹），並將該序列表示爲基數爲3的數字（或者可能是可變基數會更合適）。

但是對於二叉搜索樹，並不是每個元素的組織都是可以接受的。您還必須遵守數字排序約束。另一方面，由於二進制搜索樹中的插入定義良好，因此可以通過以特定的插入順序包含N個數字列表來表示一個包含N個元素的整個樹。通過將數字排列成不同的順序，您可以生成不同的樹。

排列當然很容易通過使用可變基數進行計數：第一個項目有N個選項，第二個項目有N-1個，等等。這給出了一個N個數字序列，您可以編碼爲一個數字基數從N變化到1.從可變基到二進制或十進制的編碼和解碼可以從普通的固定基轉換算法中簡單地調整。 （使用模數和除法運算的）。

所以，你可以一個數轉換和置換，並從和向二叉搜索樹提供的數字，你可以轉換（即列表）排列的列表。現在我認爲你可以通過排列整數1到N來獲得所有可能的大小爲N的二叉搜索樹，但我並不完全確定，並且試圖證明這篇文章有點太過分了。

我希望這是一個討論的好起點。

Answer 2

應該可以將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 + ... +道道<小號< = C0 + C1 + C2 + ... +的C n + 1

則S將對應於樹n + 1個節點。所以你現在考慮P = S - （C0 + C1 + C2 + ... + Cn），它是n + 1個節點樹的枚舉中的位置。

現在我們找出的R，使得道道* C0 +的C n - 1 * C1 + .. +的C n-R 鉻< P < = CN C0 +的C n - 1 * C1 + .. +的C n-R + 1 * Cr-1

這告訴我們左子樹和右子樹有多少個節點。我們現在可以計算出精確的左子樹枚舉位置（僅考慮那個大小的樹）和精確的右子樹枚舉位置並遞歸地形成位串。

將bitstring映射到id應該類似，因爲我們知道左側子樹和右側子樹是什麼樣子，我們需要做的就是找到相應的位置並進行一些算術運算以獲得ID。

不知道它是多麼有幫助。你會一直在處理一些非常龐大的數字。