给出一个N，求中序树形。

Sample Input

1
20
31117532
0

Sample Output

X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)

这个题的思想是不断逼近。要构造一颗树，（最好）要知道他的左子树序列号和右子树序列号。这个一下子求不出来，但是我们可以先看一下能求出的东西。

N个节点数这儿有几棵树。An= C(2n, n) / (n + 1)，这个可以求，打一个表就可。且可求得N<20。

N这整棵树是几个节点。这个就好求了。用An一个一个的依次减，马上就求出来。减出来的数还得存着，待会儿还得减。

左子树几个节点。这个有点技巧了。这要明白一规律，当左子树有l个节点，右子树r个节点时，这样的树有几棵。答案是Al * Ar。这是全题的关键。而且这树是按左子树的节点树依次排下来的。这就好办了，和上面一样，一个一个挨个减下来。算出来以后右子树也出来了。这就是左子树的节点数和右子树的结点数。

最后就是这个序列号了。就拿这4,5,6,7,8来说吧。减到现在，就成了0,1,0,0,1。这有什么规律呢？没错，0,1分别是2号和3号在他们那一组（2棵树的）里的序列号。现在要用数学公式来说的话，就是：

设Sl为左边的序列号（在他们那一组里的，以下同）Sr为右边的，Al是左边节点数树的总个数，Ar同，t是N减到现在还剩的那个数。则可得：Sl = t / Ar, Sr = t  % Ar。因为每棵树是从右开始排，填满了Ar * Al种排法就结束，换到下一种Ar －1的排法里去了，也不归这个排法的管了。左边呢？就Al种排法，一个一个来，比作齿轮的话，就先得让右边的Ar轮一遍，才轮到他动一格。于是这个题就变成简单的排列组合了。

具体的算法边界处还得考虑，这个也是挺麻烦的一个地方。

#include <cstdio>

int a[20] = { 1, 1, 2, 5, 14, 42, 132,
  429, 1430, 4862, 16796, 58786, 208012,
  742900, 2674440, 9694845, 35357670,
  129644790, 477638700 }, b[20], n;

void dfs(int x)
{
 int s, l, r, i, t = x, xl, xr;
 for(i = 0; i < 20; i ++)
 {
  if(t < a[i])
   break;
  t -= a[i];
 }
 s = i - 1;
 for(i = 0; i <= s; i ++)
 {
  if(t < a[i] * a[s - i])
   break;
  t -= a[i] * a[s - i];
 }
 l = i, r = s - i;
 xl = t / a[r] + b[l], xr = t % a[r] + b[r];
 if(xl)
 {
  printf("(");
  dfs(xl);
  printf(")");
 }
 printf("X");
 if(xr)
 {
  printf("(");
  dfs(xr);
  printf(")");
 }
}

 
void init()
{
 int i, t = 0;
 b[0] = 0;
 for(i = 0; i < 19; i ++)
 {
  t += a[i];
  b[i + 1] = t;
 }
}

int main()
{
 //freopen("in.txt", "r", stdin);
 init();
 while(scanf("%d", &n) && n)
 {
  dfs(n);
  printf("\n");
 }
 return 0;
}

评论