再过几天就数据结构的考试了，看到BST那一章忍不住想做几个BST的题目，于是上次浙大月赛的题目做了一下，蛮不错的，即考察了模拟能力，又需要一些想法的目，构图是简单的，构图完成后，就有这样一个子问题需要解决：给定一颗二叉搜索树的模型（数还没有填上去），如何用已有的数来构造这棵树，可以这样想，假如根节点的值的大小为第m大，那么它的右子树的根节点的大小是什么呢？答案很显然，就是第m+1+w大（其中w表示右子树为根的左子孙的个数），同样，也可以知道左子树为根的情况，递归求解。
#include <iostream>
using namespace std;
int n;
struct point 
{
int a;
int index;
}p[ 200 ];
int cmp( const void *a, const void *b ) {
point *c = (point *)a;
point *d = (point *)b;
return c->a - d->a;
}
struct Tree {
int Data;
int Num;
int Left;
int Right;
}T[ 200 ];
int pre[ 200 ][ 200 ];
int flag;
void dfs( int key, int Index ) {
int L = T[ key ].Left;
int R = T[ key ].Right;
if( T[ key ].Data > 1 ) {
if( T[ L ].Data == 0 ) {
}else if( T[ L ].Data == 1 ) {
T[ L ].Num = p[ Index-1 ].a;
}else {
T[ L ].Num = p[ Index - 1 - T[ T[ L ].Right ].Data ].a;
dfs( L, Index - 1 - T[ T[ L ].Right ].Data );
}
if( T[ R ].Data == 0 ) {
}else if( T[ R ].Data == 1 ) {
T[ R ].Num = p[ Index+1 ].a;
}else {
T[ R ].Num = p[ Index + 1 + T[ T[ R ].Left ].Data ].a;
dfs( R, Index + 1 + T[ T[ R ].Left ].Data );
}
}
}
void DFS( int key ) {
int L = T[ key ].Left;
int R = T[ key ].Right;
if( T[ key ].Data > 1 ) {
if( T[ L ].Data )
DFS( L );
if( T[ R ].Data )
DFS( R );
}
if( flag ++ ) {
printf(" ");
}
printf( "%d", T[ key ].Num );
}
int main() {
int i, j;
int L, las, now;
int t;
while( scanf("%d", &n) != EOF ){
flag = 0;
for(i = 0; i < n; i++) {
scanf("%d", &p[i].a);
p[i].index = i;
}
qsort( p, n, sizeof( point ), cmp );
scanf("%d", &L);
t = 1;
T[ 0 ].Data = 0;
las = 0;
pre[ 0 ][ las ++ ] = t++;
T[ 1 ].Data = n;
now = 0;
for(i = 1; i < L; i++) {
for(j = 0; j < las; j++) {
int p;
scanf("%d", &p);
T[ pre[i-1][ j ] ].Left = t++;
T[ t-1 ].Data = p;
if( p > 1 ) {
pre[i][ now++ ] = t-1;
}
scanf("%d", &p);
T[ pre[i-1][ j ] ].Right = t++;
T[ t-1 ].Data = p;
if( p > 1 ) {
pre[i][ now++ ] = t-1;
}
}
las = now;
now = 0;
}
if( n == 1 ) {
printf("%d\n", p[0].a);
continue;
}
T[ 1 ].Num = p[ T[ T[1].Left ].Data ].a;
dfs( 1, T[ T[1].Left ].Data );
DFS( 1 );
puts("");
}
}