请教大家一道ACM题目?
http://acm.zju.edu.cn/show_problem.php?pid=2738
The Kth BST
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:
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.
In this problem, we just care about the Preorder Traversal of a BST. Here is the pseudocode for Preorder Traversal:
void preorder(tree_pointer ptr)
/* preorder tree traversal */
{
if (ptr) {
printf( "%d ", ptr-> data);
preorder(ptr-> left_child);
preorder(ptr-> right_child);
}
}
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:
a b
\ /
b a
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:
n is between 1 and 19
K is between 1 and the number of ways to construct the BST
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
2 2
4 9
Sample Output
ba
a * *
b a *
cbad
a * *
b a *
c b d
d * *
题目大意就是说一棵有n个结点(全由小写字母从a开始组成)的二叉搜索树,如果按先序遍历,那么将得到
C(2n,n)
--------- 种结果, 现在要求第K个组合是什么?
n+1
我想到的方法是从先从n个字母中选一个根结点,那它的左右两子树组合成的结果就有
C(2*(t-1),t-1) C(2*(n-t),n-t)
-------------- * ------------- 种 , t表示第t个字母. 再从左右子树中
t n-t+1
再选一个根结点.
不过这样实现起来挺复杂的. 大家有好的算法吗? 谢谢!
[解决办法]
我上面已经说了，“具体的，可以以i=0，i=1，... 地将b[i]*b[n-i-1]加在当前和sum上，直至sum> =b[n]。”这个时候，说明要求的二叉树形状是左子树有i个节点，右子树有n-i-1个节点。
然后，再对b[i]，b[n-i-1]按照上面的过程细化，就可以得出二叉树的更具体的形式了。
