#P1814. 数的序号
数的序号
题目描述
我们可以用下面的方案给二叉树标号:
- 空树的序号为 。
- 只有一个根结点的树序号为 。
- 所有包含 个结点的二叉树的序号一定比任何一个包含 个结点的二叉树的序号小。
- 对于任何一棵二叉树,设其左子树序号为 ,右子树序号为 ,且它有 个结点,若它的序号为 ,则所有序号大于 的 个结点的二叉树,要么左子树序号大于 ,要么左子树序号等于 且右子树序号大于 。
例如,编号为 到 的六棵树形状如下:
0 1 2 3 4 5
X X X X X
\ / \ \
X X X X
\ /
X X
你的任务就是对给定的序号,输出该序号所对应的二叉树。
输入格式
本题有多组数据。
输入的每行有一个非负整数 , 表示输入结束,此时不需要输出 的空树。
输出格式
对于每组数据,输出一行,代表序号 对应的树。
一棵二叉树的表示为 (L)X(R)
,其中 分别是左子树和右子树的表示,如一侧为空则省略,例如只有左子树则表示为 (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)
提示
数据规模与约定
对于所有测试点,保证 ,数据组数不超过 。