〔プログラムの説明〕

次の STUDENT 構造体の配列 Stu を，身長 Height をキーとして昇順に整列して 出力する。

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

配列のデータを入れ替えずに，順番を表す 2 分木を作成する。 2 分木を表すため， 次の配列変数を定義する。

図 1 は，要素を昇順に整列したとき，要素番号が 3，1，0，5，2，4 の順番に なる場合を示す。このとき，配列 Lower，Upper の内容は 図 2 のようになる。値が −1 のときは，次に接続する要素がないことを示す。

最初に，構造体配列 Stu の定義に現れた順に要素を Upper 側に接続し，図 3 に示す 2 分木を作成する。

図３　整列前の接続状態

次に，再帰的な関数 BinTreeSort を呼び出して 2 分木の要素を身長の昇順に 整列する。引数は，ルートの要素番号である。関数 BinTreeSort の原型 （プロトタイプ）は，次のとおりである。

最後に，再帰的な関数 DisplayData を呼び出し， 2 分木をたどって構造体配列の 内容を身長の昇順に出力する。引数は，ルートの要素番号である。 関数 DisplayDataの原型は，次のとおりである。

〔プログラム〕

#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 =  ;
         if ( Stu[Data].Height >=  Stu[Root].Height ) {
                Upper[Data] =  ;
                Upper[Root] = Data ;
         }
         else    {
                Upper[Data] = Lower[Root];
                Lower[Root] =  ;　
         }
         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(  );
     printf(" 名前:%s  年齢:%d  身長:%f 体重:%f\n" ,
        Stu[Root].Name, Stu[Root].Age,
        Stu[Root].Height, Stu[Root].Weight ) ;
     DisplayData( Upper[Root] );
}