教授的测试解题报告
(tree.pas/exe)
　　　　　　　　　　　　　福州一中 石宗寅

题意描述：
　　转眼之间，新学期已经过去几个月了，F大学计算机系的W教授决定对他的学生进行一次测试。为了测试学生对树结构的认识，同时也检验他们的编程能力，教授把测试的内容定为：要求学生们编程按编号顺序打印出节点个数不少于m的所有二叉树。
　　二叉树编号规则如下：
　　仅有一个元素的树编号为1。
　　当满足以下条件之一时，定义二叉树a的编号比b大：
　　　　1． a的节点数比b多。
　　　　2． 若a的节点数与b相等，且a的左子树编号比b的左子树大。
　　　　3． a的节点数和左子树编号都和b相等，且a的右子树编号比b的右子树大。
　　二叉树的元素用大写X表示。
　　　　
　　例如：　
　　打印二叉树的格式为：
　　（ 左子树 ）{若左子树为空，则省略} X{根} （ 右子树 ）{若右子树为空，则省略}
　　例如在上图中，编号为2 的树可表示为：X（X）；
　　　　　　　　　编号为3 的树可表示为：（X）X；
　　　　　　　　　编号为5 的树可表示为：X（（X）X）；
　　当然当m较大时，检验答案对错的工作也是很繁重的，所以教授只打算对其中的若干个编号的二叉树进行抽查，他想麻烦你在测试开始前把标准答案先准备好（教授的测试卷会事先交给你）。

输入：
　　输入文件为教授的测试卷，至少1行，至多10行，每行一个数N（1<=N<=10^8）,即要抽查的二叉树的编号，以零结束。

输出：

　　输出文件是你求出的标准答案，对每一个编号输出其对应的二叉树，每个二叉树占一行，零不用输出。

样例输入（tree.in）：

　　2
　　5
　　0

样例输出（tree.out）：

　　X（X）
　　X（（X）X）

思路：

　　这是一道与树有关的题目，看到树，首先想到的是用递归的方法。
　　首先继续写出几种可能的树：
　　
　　由此可以想到，一棵有N个节点的树是由一个根节点加上一个曾在它之前出现过的节点数为１到N-1之间的树作为左子树或右子树（也可以为空，节点数为０）（如图，第（１０）号树中"包"着第（５）号树，第（５）号树中又"包"着第（３）号树）。设用aXb表示有N个节点的树的所有情况，a表示左子树有a个节点，b表示右子树有b个节点，X是根节点，那么令a＝0N-1，b＝N-1-a，用aXb就可以表示有N个节点的树的所有情况。例如，有５个节点的树是由0X4，1X3，2X2，3X1，4X0几部分组成。
　　知道了N个节点的树的组成，就可以算出节点为N的树的总数，这用递推可以实现。F（N）表示节点数为N的树的总数。计算前先令F（1）＝1，F（0）＝1，从F（2）开始递推。
　　　　　　　　　　　
　　把树的总数累加起来，就得到树的编号，如有５个节点第一种树的编号就是F（1）+F（2）+F（3）+F（4）+1，知道了树的编号，便可以知道树的节点个数了。（经过计算，编号为１０＾８的树节点不超过２０个，数据存储用字符串变量就可以了）。
　　为了说明这个问题，我来举一个例子：假设我们要求编号为44的树，由以上方程可以知道44-（F（1）+F（2）+F（3）+F（4））=22<F（5），所以44号树有5个点，并且可知，第44号树是所有5个节点的树中的第22种。对于5个点的树，就有上述0X4，1X3，2X2，3X1，4X0，几种情况，0X4的树有14种（F（a）F（b）），1X3有5种，2X2有4种……所以第22种情况就是2X2的树，并且是2X2树中的第22-14-5=3种，在把左右子树分别递归计算，设t=3，左子树就是2个点（a=2）的树中的第（（t-1）div F（b））+1种情况，右子树就是2个点（b=2）的树种的第（（t-1）mod F（b））+1种情况。依次递归。

程序：

　　program tree;
　　const max=20;
　　type arr1=array[0..max] of longint;
　　var cot:arr1;{纪录F（N）的数组}
　　　　n:longint;{编号}
　　procedure count(var sta:longint;var id:longint);
　　var t,k:longint;
　　　　f,q:longint;
　　begin
　　　　q:=n-1;
　　　　fillchar(cot,sizeof(cot),0);
　　　　cot[0]:=1;cot[1]:=1;cot[2]:=2;
　　　　t:=1;
　　　　while q>0 do
　　　　begin
　　　　　　inc(t);
　　　　　　f:=0;
　　　　　　for k:=0 to t-1 do
　　　　　　　　f:=f+cot[k]*cot[t-1-k];{递推计算F（N）}
　　　　　　cot[t]:=f;
　　　　　　q:=q-f;
　　　　end;
　　　　sta:=t;
　　　　id:=q+cot[t];
　　end;
　　function cpu(u:longint;v:longint):string;
　　{生成所有由u个点组成的树中的第v中树}
　　var s,t,m,g1,g2:longint;
　　　　st1,st2:string;
　　begin
　　　　if u=0 then begin cpu:='';exit;end;
　　　　if u=1 then begin cpu:='(X)';exit;end;
　　　　t:=v;
　　　　s:=0;
　　　　while (s<u-1) and (t-cot[s]*cot[u-1-s]>0) do
　　　　begin
　　　　　　t:=t-cot[s]*cot[u-1-s];
　　　　　　inc(s);
　　　　end;
　　　　m:=u-s-1;
　　　　g2:=((t-1) mod cot[m])+1;{右子树编号}
　　　　g1:=((t-1) div cot[m])+1;{左子树编号}
　　　　st2:=cpu(m,g2);
　　　　st1:=cpu(s,g1);
　　　　cpu:='('+st1+'X'+st2+')';
　　end;
　　var g1,z,t1:longint;
　　　　out:string;
　　　　fin,fou:text;
　　　　inp:string;
　　　　zzz:integer;
　　begin
　　　　　　　assign(fin,'tree.in');
　　　　　　　assign(fou,'tree.out');
　　　　　　　reset(fin);rewrite(fou);
　　　　　　　repeat
　　　　　　　readln(fin,inp);
　　　　　　　val(inp,n,zzz);
　　　　　　　if n<>0 then begin
　　　　　　　count(g1,t1);{计算编号为n的树的节点数g1和编号n的树属于g1个点的所有树的第t1种情况}
　　　　　　　out:=cpu(g1,t1);{生成字符串}
　　　　　　　delete(out,1,1);
　　　　　　　delete(out,length(out),1);
　　　　　　　writeln(fou,out);
　　　　　　　end;
　　　　　　　until n=0;
　　　　　　　close(fin);close(fou);
　　end.