#P2274. [HNOI2002] 树的排序

    ID: 1286 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>排序选择排序各省省选2002湖南

[HNOI2002] 树的排序

题目描述

  1. 空树编号为 00,只有根节点的树编号为 11
  2. mm 为一任意非负整数,那么任意一棵有 mm 个节点的树的编号小于任意一棵有 m+1m+1 个节点的树;
  3. A,BA,B 是两棵节点数相同的树(A,BA,B 不相同),则 AA 编号比 BB 小时,一定满足下面两个条件之一(反之亦然):
    1. AA 左子树编号小于 BB 左子树编号;
    2. AA 左子树编号等于 BB 左子树编号(即 A,BA,B 左子树形态相同),且 AA 右子树编号小于 BB 右子树编号;
  4. 编号按照正常的规则,编号应是连续的非负整数,任意一棵树唯一对应一个编号,任意一个非负整数唯一对应一棵树。

(注:上述树均指二叉树)

输入格式

11 行,为一个整数 nn1n500,000,0001\le n\le 500{,}000{,}000

对于 10%10\% 的数据,保证树节点个数不超过三个。

输出格式

11 行,为对应编号为 nn 的二叉树。按下列方式输出:

  • 如果是一个结点的二叉树,则输出 XX
  • 如果二叉树的左、右子树分别为 LLRRL,RL,R 的输出形式分别为 LL'RR',则输出为 (L)X(R)\texttt{(}L'\texttt{)}X\texttt{(}R'\texttt{)},当左子树为空时,输出为 X(R)X\texttt{(}R'\texttt{)},当左子树为空时 (L)X\texttt{(}L'\texttt{)}X
20
((X)X(X))X