[ACM] The Kth BST (较难)

无言的梦

(也是那次比赛的)

Time limit: 1 Seconds   Memory limit: 32768K

-------------------------------------------

Definition: A binary tree is a finite set of nodes that is either empty or consists of a root and two disjoint binary trees called the left subtree and the right subtree.

Definition: A binary search tree(BST) is a binary tree. It may be empty. If it is not empty, it satisfies the following properties:

<OL>

Every elements has a key, and no two elements have the same key, that is, the keys are unique.

The keys in a nonempty left subtree must be smaller than the key in the root of the subtree.

The keys in a nonempty right subtree must be larger than the key in the root of the subtree.

The left and right subtrees are also binary search trees. </OL>
In this problem, we just care about the Preorder Traversal of a BST. Here is the pseudocode for Preorder Traversal:
<PRE>void preorder(tree_pointer ptr)
/* preorder tree traversal */
{
    if (ptr) {
        printf("%d", ptr->data);
        preorder(ptr->left_child);
        preorder(ptr->right_child);
    }
}
</PRE>
Now, you are given n, the number of nodes in a BST, and the nodes of the BST are consist of the first n lowcase letters. Of course, more than one BST can be constructed except when n is 1. You task is to sort there BST's according to their preorder representations, and gives out the Kth BST.

For example, when n is 2, there are two BST's can be constructed, as following:
<PRE>a     b
\   /
  b a
</PRE>
Their preorder representations are: ab and ba, so the first one is ab, and the second one is ba.

Input

There are multiple test cases in this problem. The input is terminated by EOF.

For each test case, there are two inputs: n and K, representing the number of nodes in the BST, and the index of the BST you need to output.

Note:

<UL>

n is between 1 and 19

K is between 1 and the number of ways to construct the BST </UL>
Output

For each input, you should first output the Kth preorder representation of the BST. Next, for each node (in the order a, b, c, ...), output it first, then output the left sub node (output * if not exist) and the right sub node (output * if not exist), seperated by a single blank space. K will not be greater than the number of representations of BST given n nodes. Output a blank line between two test cases.

Sample Input
<PRE>2 2
4 9
</PRE>
Sample Output
<PRE>ba
a * *
b a *

cbad
a * *
b a *
c b d
d * *
</PRE>
Author: DAI, Wenbin