2013
11-09

# POJ 1095 Trees Made to Order [解题报告] Java

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)

//* @author: ccQ.SuperSupper
import java.io.*;
import java.util.*;

public class Main {
static final int N = 20+10;
static int sum[] = new int[N],catana[] = new int[N];
static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
public static void main(String[]args) throws Exception{
int n;
init();
Scanner cin = new Scanner(System.in);
while(true){
n = cin.nextInt();
if(n==0) break;
solve(n);
out.println();
out.flush();
}
}
static void solve(int n){
int i,j,t;
if(n==0) return ;
if(n==1) {out.print("X");return;}
for(j=1;;++j){
if(sum[j]>=n) break;
}
n = n-sum[j-1];
for(i=0;i< j;++i){
t = catana[i]*catana[j-i-1];
if(n>t) n = n-t;
else break;
}
if(i!=0){
out.print("(");
solve(sum[i-1]+1+(n-1)/catana[j-i-1]);
out.print(")");
}
out.print("X");
if(i!=j-1){
out.print("(");
solve(sum[j-2-i]+1+(n-1)%catana[j-i-1]);
out.print(")");
}
}
static void init(){
int i,j;
catana[0] = catana[1] = 1;
for(i=2;i< N;++i){
catana[i] = 0;
for(j=0;j< i;++j){
catana[i] += catana[j]*catana[i-j-1];
}
}
sum[0] = 0;
sum[1] = 1;
for(i=2;i< N;++i)
sum[i] = sum[i-1]+catana[i];
}
}

1. 很高兴你会喜欢这个网站。目前还没有一个开发团队，网站是我一个人在维护，都是用的开源系统，也没有太多需要开发的部分，主要是内容整理。非常感谢你的关注。