We can number binary trees using the following scheme:
The empty tree is numbered 0.
The single-node tree is numbered 1.
All binary trees having m nodes have numbers less than all those having m+1 nodes.
Any binary tree having m nodes with left and right subtrees L and R is numbered n such that all trees having m nodes numbered > n have either
Left subtrees numbered higher than L, or
A left subtree = L and a right subtree numbered higher than R.
The first 10 binary trees and tree number 20 in this sequence are shown below:
Your job for this problem is to output a binary tree when given its order number.
Input
Input consists of multiple problem instances. Each instance consists of a single integer n, where 1 <= n <= 500,000,000. A value of n = 0 terminates input. (Note that this means you will never have to output the empty tree.)
Output
For each problem instance, you should output one line containing the tree corresponding to the order number for that instance. To print out the tree, use the following scheme:
A tree with no children should be output as X.
A tree with left and right subtrees L and R should be output as (L')X(R'), where L' and R' are the representations of L and R.
If L is empty, just output X(R').
If R is empty, just output (L')X.
Sample Input
1
20
31117532
0
Sample Output
X
((X)X(X))X
(X(X(((X(X))X(X))X(X))))X(((X((X)X((X)X)))X)X)
思路：
a數組表示節點數為j所能表示最大的數。
則第j個節點所能表示的數a[j]符合卡特蘭數：
a[j] = a[0] * a[j - 1] + a[1] * a[j - 2] + ...... + a[j - 1] * a[0];
表示：有j個節點 = 左邊0個節點的個數 * 右邊j - 1個節點的個數 + ...... + 左邊j - 1個節點的個數 * 右邊0個節點的個數。
之后根據讀入的n，判斷出節點數，在再判斷出左右的節點數和左右所代表的數。
然后調用遞歸。
#include <cstdio>
#include <cstring>
using namespace std;
int a[25], b[25];
void solve(int n)
{
int t, i, j;
if (n == 0) return;
if (n == 1)
{
printf("X");
return;
}
for (j = 1;; ++j)
{
if (b[j] >= n)
break;
}
n = n - b[j - 1];
for (i = 0; i < j; ++i)
{
t = a[i] * a[j - 1 - i];
if (n > t)
{
n = n - t;
}
else
break;
}
if (i != 0)
{
printf("(");
solve(b[i - 1] + 1 + (n - 1)/ a[j - 1 - i]);
printf(")");
}
printf("X");
if (i != j - 1)
{
printf("(");
solve(b[j - 2 - i] + 1 + (n - 1) % a[j - 1 - i]);
printf(")");
}
}
int main()
{
int n;
int i, j;
b[0] = 0;
a[0] = b[1] = a[1] = 1;
for (i = 2; i < 20; ++i)
{
a[i] = 0;
for (j = 0; j < i; ++j)
{
a[i] += a[j] * a[i - j - 1];
}
b[i] = b[i - 1] + a[i];
}
while (scanf("%d", &n) && n)
{
solve(n);
printf("\n");
}
return 0;
}
posted on 2011-10-25 20:55
LLawliet 閱讀(416)
評論(0) 編輯 收藏 引用 所屬分類:
數論