/*
    第２種情報処理技術者試験    平成11年度・秋期・午後 問7
                                BohYoh Shibata PREPARATION
*/

#include      <stdio.h>

void      BinTreeSort( int  Root ) ;
void      DisplayData( int  Root ) ;

#define MAXNUM    5

typedef struct {
    char      Name[64] ;  /*  名前      */
    int       Age ;       /*  年齢      */
    float     Height ;    /*  身長      */
    float     Weight ;    /*  体重      */
    } STUDENT ;

STUDENT Stu[MAXNUM] = {
    { "相川 太郎", 19, 162.5, 65.4 },
    { "伊藤 四郎", 14, 158.0, 48.4 },
    { "加藤 五郎", 18, 182.0, 82.5 },
    { "田中 三郎", 12, 148.0, 46.8 },
    { "山中 次郎", 16, 178.5, 70.0 } } ;
int Upper[MAXNUM], Lower [MAXNUM] ;

main( )
{
     int Index ;
     for( Index = 0 ; Index < MAXNUM ;  Index++ ) {
          Upper[Index] = Index + 1 ;
          Lower[Index] = -1 ;
     }
     Upper[MAXNUM - 1] = -1 ;
     BinTreeSort( 0 );
     DisplayData( 0 );
}

void  BinTreeSort( int  Root )
{
     int Data, Next ;

     Data = Upper[Root] ;
     if ( Data == -1 )  return ;
     Upper[Root] = -1 ;
     while( Data != -1 ) {
         Next = Upper[Data] ;
         if ( Stu[Data].Height >=  Stu[Root].Height ) {
                Upper[Data] = Upper[Root] ;
                Upper[Root] = Data ;
         }
         else    {
                Upper[Data] = Lower[Root] ;
                Lower[Root] = Data ;
         }
         Data = Next;
      }
      Data = Upper[Root] ;
      if ( Data != -1 )  BinTreeSort( Data );
      Data = Lower[Root] ;
      if ( Data != -1 )  BinTreeSort( Data );
}

void  DisplayData( int  Root )
{
     if ( Root == -1 ) return ;
     DisplayData( Lower[Root] );
     printf(" 名前:%s  年齢:%d  身長:%f 体重:%f\n" ,
        Stu[Root].Name, Stu[Root].Age,
        Stu[Root].Height, Stu[Root].Weight ) ;
     DisplayData( Upper[Root] );
}