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