【题意】
给有根二叉树标号,遵循以下原则
1、空树为0
2、k个节点的树标号小于k+1个节点的树
3、两个节点相同的树A和B,A的标号大于B,当且仅当((A的左子树比B的左子树标号大)或(A的左子树标号和B的左子树标号相同且A的右子树标号比B的右子树标号大))
前几组标号形态如下
给定标号,输出对应的树
【输入】
多组数据,每组数据一个n表示树的标号
【输出】
对于每组数据,输出对应的树的中序表示法
首先有根二叉树的总数对应着卡特兰数
原理
令h(1)=1,h(2)=1,catalan数满足递归式:
h(n)= h(1)*h(n-1)+h(2)*h(n-2) + ... + h(n-1)h(1) (其中n>=3)
例如:h(3)=h(1)*h(2)+h(2)*h(1)=1*1+1*1=2
h(4)=h(1)*h(3)+h(2)*h(2)+h(3)*h(1)=1*2+1*1+2*1=5
另类递归式: h(n)=h(n-1)*(4*n-2)/(n+1);
该递推关系的解为: h(n)=C(2n,n)/(n+1) (n=1,2,3,...)
n各节点的有根二叉树个数就对应着h[n+1],为什么这么对应,也是比较好理解的
对于这道题,我们可以用分治的思想来做
已知当前树的标号,就可以求出来其左子树和右子树的标号
那么该树的中序表达式即为(L)X(R),递归调用即可
这个怎么具体求,想的十分麻烦,这种规律性的最令人头疼了
program poj1095; const l:array [0..19] of int64=(1,1,2,5,14,42,132,429,1430,4862,16796,58786, 208012,742900,2674440,9694845,35357670,129644790,477638700,1767263190); var i,n:longint; sum:array [-1..19] of int64; function solve (now:longint):ansistring; var i,k,q,p:longint; s:int64; ans:ansistring; begin if now=0 then exit(''); if now=1 then exit('X'); for i:=0 to 19 do if sum[i]>=now then break; k:=i; now:=now-sum[k-1]; s:=0; for i:=0 to k-1 do if s+l[i]*l[k-i-1]>=now then break else s:=s+l[i]*l[k-i-1]; q:=i; now:=now-s; ans:=''; if q<>0 then ans:=ans+'('+solve(sum[q-1]+(now-1) div l[k-q-1]+1)+')'; ans:=ans+'X'; if k-q-1<>0 then ans:=ans+'('+solve(sum[k-q-2]+(now-1) mod l[k-q-1]+1)+')'; exit(ans); end; begin sum[-1]:=0; for i:=0 to 19 do sum[i]:=sum[i-1]+l[i]; repeat read(n); if n=0 then break; writeln(solve(n+1)); until false; end.