英雄哪里出來(lái)

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