再過幾天就數(shù)據(jù)結(jié)構(gòu)的考試了，看到BST那一章忍不住想做幾個(gè)BST的題目，于是上次浙大月賽的題目做了一下，蠻不錯(cuò)的，即考察了模擬能力，又需要一些想法的目，構(gòu)圖是簡單的，構(gòu)圖完成后，就有這樣一個(gè)子問題需要解決：給定一顆二叉搜索樹的模型（數(shù)還沒有填上去），如何用已有的數(shù)來構(gòu)造這棵樹，可以這樣想，假如根節(jié)點(diǎn)的值的大小為第m大，那么它的右子樹的根節(jié)點(diǎn)的大小是什么呢？答案很顯然，就是第m+1+w大（其中w表示右子樹為根的左子孫的個(gè)數(shù)），同樣，也可以知道左子樹為根的情況，遞歸求解。
#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("");
}
}