摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

建立二元搜尋樹  必要時做調整  這題貌似不用

直接跑中序搜尋結果?

/***********************************************************/

#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;
}