急寻高手解释一个程序!题目是PKU2775DescriptionManypeopleknowsbinarysearchtree.ThekeysinabinarysearchtreearealwaysstoredinsuchawayastosatisfytheBSTproperty:LetXbeanodeinabinarysearchtree.IfYis

Question

急寻高手解释一个程序!
题目是PKU 2775
【Description】
Many people knows binary search tree. The keys in a binary search tree are always stored in such a way as to satisfy the BST property: Let X be a node in a binary search tree. If Y is a node in the left subtree of X , then Y X. For example,
It is a binary search tree. And it can be built by inserting the elements of vector A= (12, 6, 3, 18, 20, 10, 4, 17, 20) sequentially. But it can also be built by the vector B= (12, 18, 17, 6, 20, 3, 10, 4, 20). Now given a vector X, then you may get a binary search tree from X. Your job is to calculate how many different vectors can build the same binary search tree. To make it easy, you should just output the number of different vectors mod 9901.
【Input】
Input consists of several cases. Each case starts with a line containing one positive integer n, which is the length of test vector. The integer n is less than 20. Following this there will be n positive integers, which are less then 1000, on the next line. The input will end with a case starting with n = 0. This case should not be processed.
【Output】
For each test case, print a line with a single integer, which is the number of different vectors mod 9901.
【Sample Input】
3
2 1 3
9
5 6 3 18 20 10 4 17 20
0
【Sample output】
2
168
下面是我在网上找到的一个代码,本人是菜鸟,程序没有注释,看不懂,哪位高手能够帮忙给程序添加一些详细的注释,万分感谢,请先说一下这个题目的思路!
#include
#include
const int max=20025;
int tree[max],size[max];
int da[10001];
int an;
void insert(int x)
{
int p,y;
p=1;y=1;
//查找
while(size[p]!=0)
{
size[p]++;y=p;
if(x

Answer 1

这是个二叉树搜索算法,分为左子树和右子树进行分叉搜索.
关键函数：void lookup(int p)
关键句：
if(size[2*p+1]+size[2*p]==0)return;
if(size[2*p]) lookup(2*p);
if(size[2*p+1]) lookup(2*p+1);
主程序中先将输入的数据构造成树,然后进行搜索,invx是个计算符合条件数据的函数.
不好意思,这东西我自己看了也想吐,就帮你这么多吧,我得去呕了.