递归构造答案。
根据当前整颗树的编号，可以计算左右子树有几个节点以及编号。因此，不断dfs下去就可以了。
#include#include #include #include using namespace std;long long c[20] = { 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786,208012, 742900, 2674440, 9694845, 35357670, 129644790 };long long n;void dfs(long long num, long long p){ long long left=0, right=0, sum = 0,left_p, right_p; int level = (int)num; for (int i = 0; i <= level-1; i++) { sum = sum + c[i] * c[level - 1 - i]; if (sum >= p) { sum = sum - c[i] * c[level - 1 - i]; p = p - sum; left = (long long)i; right = (long long)(level - 1 - i); if (c[level - 1 - i] == 1) left_p = p / c[level - 1 - i]; else left_p = p / c[level - 1 - i] + 1; right_p = p% c[level - 1 - i]; if (right_p == 0) right_p = c[level - 1 - i]; break; } } if (left != 0){printf("(");dfs(left, left_p);printf(")");} printf("X"); if (right != 0){printf("(");dfs(right, right_p);printf(")");}}void work(){ long long p, left, right, sum = 0,left_p=0, right_p=0; int level; for (int i = 1; i <= 17; i++) { sum = sum + c[i]; if (sum >= n){ sum = sum - c[i]; level = i; p = n - sum; break; } } dfs((long long)level, p); printf("\n");}int main(){ while (~scanf("%lld", &n)) { if (!n) break; work(); } return 0;}