2013
11-27

# Trees Made to Order

We can number binary trees using the following scheme:
The empty tree is numbered 0.
The single-node tree is numbered 1.
All binary trees having m nodes have numbers less than all those having m+1 nodes.
Any binary tree having m nodes with left and right subtrees L and R is numbered n such that all trees having m nodes numbered > n have either
Left subtrees numbered higher than L, or
A left subtree = L and a right subtree numbered higher than R.The first 10 binary trees and tree number 20 in this sequence are shown below:
Your job for this problem is to output a binary tree when given its order number.

Input consists of multiple problem instances. Each instance consists of a single integer n, where 1 <= n <= 500,000,000. A value of n = 0 terminates input. (Note that this means you will never have to output the empty tree.)

For each problem instance, you should output one line containing the tree corresponding to the order number for that instance. To print out the tree, use the following scheme:A tree with no children should be output as X.
A tree with left and right subtrees L and R should be output as (L’)X(R’), where L’ and R’ are the representations of L and R.
If L is empty, just output X(R’).
If R is empty, just output (L’)X.

1
20
31117532
0

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

http://acm.hdu.edu.cn/showproblem.php?pid=1100

#include <cstdio>
#include <cstring>

typedef __int64 ll;
const int maxn = 20;
const ll maxsum = 500000000;
ll tri[maxn << 1][maxn << 1];
ll sum[maxn], rec[maxn];
int cur, l[maxn], r[maxn];

void build(){
memset(tri, 0, sizeof(tri));
tri[0][0] = 1;
for (int i = 1; i < maxn << 1; i++){
tri[i][0] = 1;
for (int j = 1; j <= i; j++){
tri[i][j] = tri[i - 1][j - 1] + tri[i - 1][j];
}
}
sum[0] = rec[0] = 1;
for (int i = 1; i < maxn; i++){
rec[i] = tri[i << 1][i] / (i + 1);
sum[i] = sum[i - 1] + rec[i];
#ifndef ONLINE_JUDGE
printf("%2d : %12I64d %12I64d\n", i, sum[i], rec[i]);
#endif
}
}

void con(int rt, int rest, int cnt){
if (rest == 1 && cnt == 1){
return ;
}
cnt--;
for (int i = 0; i <= cnt; i++){
int tmp = rec[i] * rec[cnt - i];

if (rest > tmp) rest -= tmp;
else{
int lrest = (rest - 1) / rec[cnt - i] + 1;
int rrest = (rest - 1) % rec[cnt - i] + 1;

if (i){
l[rt] = ++cur;
con(cur, lrest, i);
}
if (cnt - i){
r[rt] = ++cur;
con(cur, rrest, cnt - i);
}

break;
}
}
}

void print(int rt){
if (~l[rt]){
putchar('(');
print(l[rt]);
putchar(')');
}
putchar('X');
if (~r[rt]){
putchar('(');
print(r[rt]);
putchar(')');
}
}

void deal(int n){
int cnt = 0;

while (n >= sum[cnt]) cnt++;
#ifndef ONLINE_JUDGE
printf("%d\n", cnt);
#endif
for (int i = 0; i < cnt; i++)
l[i] = r[i] = -1;
cur = 0;
n -= sum[cnt - 1] - 1;
con(0, n, cnt);
print(0);
puts("");
}

int main(){
int n;

build();
while (~scanf("%d", &n) && n)
deal(n);

return 0;
}

——written by Lyon

1. a是根先忽略掉，递归子树。剩下前缀bejkcfghid和后缀jkebfghicd，分拆的原则的是每个子树前缀和后缀的节点个数是一样的，根节点出现在前缀的第一个，后缀的最后一个。根节点b出现后缀的第四个位置，则第一部分为四个节点，前缀bejk，后缀jkeb，剩下的c出现在后缀的倒数第2个，就划分为cfghi和 fghic，第3部分就为c、c

2. 博主您好，这是一个内容十分优秀的博客，而且界面也非常漂亮。但是为什么博客的响应速度这么慢，虽然博客的主机在国外，但是我开启VPN还是经常响应很久，再者打开某些页面经常会出现数据库连接出错的提示