快速排序. (非快排版)
建立二元搜尋樹 必要時做調整 這題貌似不用
直接跑中序搜尋結果?
/***********************************************************/
#include<stdio.h>
#include<stdlib.h>
int NUM[200001]={0};
int link[200001][2]={0},top,MAX;
int rl[200001][2]={0};
void Tree(int now,int value,int L)
{
if(L>MAX) MAX=L;
if(value>NUM[now])
{
if(link[now][1]==0)
link[now][1]=++top,NUM[top]=value,rl[now][1]++;
else
Tree(link[now][1],value,L+1);
}
else
{
if(link[now][0]==0)
link[now][0]=++top,NUM[top]=value,rl[now][0]++;
else
Tree(link[now][0],value,L+1);
}
}
int s[200000],stop=0;
void treesort(int now)
{
if(link[now][0]!=0) treesort(link[now][0]);
s[stop++]=NUM[now];
if(link[now][1]!=0) treesort(link[now][1]);
}
void putin(int l,int h,int flag)
{
if(l>h) return;
int m=(l+h)/2;
if(flag==1) NUM[1]=s[m];
else Tree(1,s[m],0);
putin(l,m-1,0);
putin(m+1,h,0);
}
void balance()
{
stop=0,top=1;
treesort(1);
int a;
for(a=0;a<=stop;a++) link[a][0]=0,link[a][1]=0,NUM[a]=0,rl[a][0]=0,rl[a][1]=0;
putin(0,stop-1,1);
}
void Findk(int now,int k)
{
if(k-1>rl[now][0])/*往右邊搜*/
Findk(link[now][1],k-rl[now][0]-1);
else if(k-1<rl[now][0])/*往左邊搜*/
Findk(link[now][0],k);
else printf("%d\n",NUM[now]);
}
void print(int now)
{
if(link[now][1]!=0) print(link[now][1]);
printf("%d ",NUM[now]);
if(link[now][0]!=0) print(link[now][0]);
}
main()
{
int M;
scanf("%d",&M);
NUM[1]=M,top=1;
while(scanf("%d",&M)!=EOF)
{
MAX=0;
Tree(1,M,0);
if(MAX>50)
balance();
}
print(1);
return 0;
}
上一篇:文文的求婚 (三)