教授的测试（二叉树计数）

admin

一年一度的研究生面试又快要来临了。为了测试学生对树结构的认识，同时也检验他们的编程能力，福州大学计算机系把面试的一项内容定为：要求学生们编程按编号顺序打印出节点个数不少于m的所有二叉树。
二叉树编号规则如下：
仅有一个节点的树编号为1。
当满足以下条件之一时，定义二叉树a的编号比b大：
   1. a的节点数比b多。
   2. 若a的节点数与b相等，且a的左子树编号比b的左子树大。
   3. a的节点数和左子树编号都和b相等，且a的右子树编号比b的右子树大。
二叉树的节点用大写X表示，例如：

当然当m较大时，检验答案对错的工作也是很繁重的，所以教授只打算对其中的若干个编号的二叉树进行抽查，他想麻烦你编制一个程序能够产生编号为n的二叉树的标准答案。
Input 输入数据由多组数据组成。每组数据仅一个整数，表示n (1≤n≤10^8)的值。输入数据以n=0表示结束，该数据不要处理。
Output 对于每组数据，输出仅一行，即你求出的标准答案。
二叉树的输出格式为：
(左子树){若左子树为空则省略}X{根}(右子树){若右子树为空则省略}
其中{…}中的内容是说明，不必输出。例如，在上图中编号为5的树可表示为X((X)X)；编号为6的树表示为(X)X(X)。
Sample Input
20
0

Sample Output
((X)X(X))X

admin

来一组测试数据
输入
2727
45678
80270
12163
82596
53868849
66951445
95227629
98046525
1154205
0
输出
X((X((X)X))X(((X(X))X)X))
(X(X))X(X((X(X((X(X(X)))X)))X))
((((X(X))X((X)X))X((X(X))X))X)X
(X)X(X((((X((X)X))X)X(X))X))
X(X(X(X(X(X((X((X)X((X)X)))X))))))
X(X(((((X((X)X))X(X))X(X))X)X((X((X(X))X))X(X))))
X(((((X)X)X((X)X(X(X))))X)X(X(X((X)X((X(X))X)))))
(X(X))X(((X)X((X((X)X))X(X(X))))X(((X)X(X))X(X)))
((X)X)X((((X)X(X))X(X((X((X(X))X))X)))X((X)X(X)))
X(X(((X((X)X(X(((X)X)X))))X)X((X)X(X))))

admin

1. #include <bits/stdc++.h>
   
2. using namespace std;
   
3. const int catalan[18] = {1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, 2674440, 9694845, 35357670, 129644790};
   
4. int n;
   
5. int nodes(int x)
   
6. {
   
7.         int sum = 0;
   
8.         for (int i=1; i<=17; i++)
   
9.         {
   
10.                 sum += catalan[i];
    
11.                 if (sum>x) return i;
    
12.         }
    
13.         return 18;
    
14. }
    
15. 
    
16. void dfs(int node,int x)
    
17. {
    
18.         if (node==0) return ;
    
19.         if (node==1)
    
20.         {
    
21.                 cout<<"X";
    
22.                 return ;
    
23.         }
    
24.         int temp_no = x;
    
25.         int left = 0,right = node - 1;
    
26.         while (1)
    
27.         {
    
28.                 int temp;
    
29.                 if ((temp = catalan[left]*catalan[right])>=temp_no)
    
30.                         break;
    
31.                 temp_no -= temp;
    
32.                 left ++;
    
33.                 right --;
    
34.         }
    
35.         if (left>0)
    
36.         {
    
37.                 cout<<"(";
    
38.                 dfs(left,(temp_no - 1)/catalan[right] + 1);
    
39.                 cout<<")";
    
40.         }
    
41.         cout<<"X";
    
42.         if (right>0)
    
43.         {
    
44.                 cout<<"(";
    
45.                 dfs(right,(temp_no - 1)%catalan[right] + 1);
    
46.                 cout<<")";
    
47.         }
    
48. }
    
49. 
    
50. int main()
    
51. {
    
52.         cin>>n;
    
53.         int node = nodes(n);
    
54.         int temp = n;
    
55.         for (int i=1; i<node; i++)
    
56.                 temp -= catalan[i];
    
57.         dfs(node,temp);
    
58.         return 0;
    
59. }

复制代码