随笔 - 97, 文章 - 22, 评论 - 81, 引用 - 0
数据加载中……

Zju 3170 7 Levels of Binary Search Tree (BST 应用)

            再过几天就数据结构的考试了,看到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 
*= (point *)a;
    point 
*= (point *)b;
    
return c->- 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(
"");
    }

}

posted on 2009-06-05 02:42 英雄哪里出来 阅读(425) 评论(1)  编辑 收藏 引用 所属分类: ACM

评论

# re: Zju 3170 7 Levels of Binary Search Tree (BST 应用)  回复  更多评论   

谢谢你,前辈。
2016-06-08 01:29 | 破军

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理