首页 > 专题系列 > Java解POJ > POJ 1095 Trees Made to Order [解题报告] Java
2013
11-09

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

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)

解题代码:

//* @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. 很高兴你会喜欢这个网站。目前还没有一个开发团队,网站是我一个人在维护,都是用的开源系统,也没有太多需要开发的部分,主要是内容整理。非常感谢你的关注。