Binary Tree ソート

Binary Tree で昇順にソートして印字します。
Binary Tree Sort は「データの入れ替え」が不要で、サイズの大きなレコードのソートなどに威力を発揮します。

前田稔(Maeda Minoru)の超初心者のプログラム入門

Binary Tree を昇順に印字

List 構造の基礎は List 連鎖の基礎 を参照して下さい。

Binary Tree の構造体

struct  TREE
{   struct  TREE    *car;
    struct  TREE    *cdr;
    int     v;
};
car 自分より小さいデータを格納する構造体へのポインタ
cdr 自分より大きいデータを格納する構造体へのポインタ
v ソートのキー項目

Test Data の定義

Binary Tree 構造体をテストするために、一個ずつ定義してみました。
  struct  TREE    t2= { NULL,NULL,1 };
  struct  TREE    t4= { NULL,NULL,3 };
  struct  TREE    t5= { NULL,NULL,5 };
  struct  TREE    t3= { &t4, &t5, 4 };
  struct  TREE    t1= { &t2, &t3, 2 };
  struct  TREE    *PT= &t1;
宣言の順序が前後していますが BinaryTree 構造の TestData です。
*PT Binary Tree 構造の親ポインタで t1 を指します
t1 v=2 で、t2(小さい)とt3(大きい)をポイントします
t2 v=1 で、下位の構造はありません
t3 v=4 で、t4(小さい)とt5(大きい)をポイントします
t4 v=3 で、下位の構造はありません
t5 v=5 で、下位の構造はありません

Binary Tree をたどって昇順に表示

BinaryTree 構造をたどって昇順に表示するプログラムです。
テストするデータは、一個ずつ定義しているので不細工ですが、list() 関数は再起を使って非常にシンプルなソースコードに仕上がっています。
/*★ Binary Tree を昇順に印字する    前田　稔 ★*/
#include    <stdio.h>

struct  TREE
{   struct  TREE    *car;
    struct  TREE    *cdr;
    int     v;
};

struct  TREE    t2= { NULL,NULL,1 };
struct  TREE    t4= { NULL,NULL,3 };
struct  TREE    t5= { NULL,NULL,5 };
struct  TREE    t3= { &t4, &t5, 4 };
struct  TREE    t1= { &t2, &t3, 2 };
struct  TREE    *PT= &t1;

// Binary Tree を昇順に表示
void    list(struct TREE *pt)
{
    if (pt==NULL)   return;
    if (pt->car!=NULL)  list(pt->car);
    printf("%5d",pt->v);
    if (pt->cdr!=NULL)  list(pt->cdr);
}

//☆ MAIN
int     main()
{
    list(PT);
    printf("\nEnd Data\n");
    return 0;
}

配列に格納されたデータをソート

ソートするデータを配列で定義して、sort() 関数に渡します。
sort() 関数では、t[n] のデータを BinaryTree 形式に連鎖しながら格納します。
一件のデータを BinaryTree に追加する関数が app() で、TR[i].v に t[i] の値を格納して連鎖します。
最初に登録したデータほど深くに格納され TREE *PT; は最後に格納したセルをポイントしています。
リストが完成すると先に説明した list() で昇順に表示して下さい。
#define     MAX     100
struct  TREE    *PT;
struct  TREE    TR[MAX];
int             t[MAX] = { 10, 7, 2, 10, 5, 3, 6, 9, 1, 4, 8 };
            ：
void    sort(int t[], int n)
{   int     i;

    PT= NULL;
    for(i=0; i<n; i++)
    {   TR[i].car=TR[i].cdr= NULL;
        TR[i].v= t[i];
        app(&PT,&TR[i]);
    }
}

Binary Tree にデータを一件追加

先に説明したような規則に従ってデータがセットされた構造体を連鎖して行きます。
void    app(struct TREE **pt, struct TREE *w)
{
    if (*pt==NULL)      {   *pt= w;  return;  }
    if ((*pt)->v > w->v)    app(&(*pt)->car,w);
    else                    app(&(*pt)->cdr,w);
}

【演習】

  1. ソースコードは極めてシンプルですがプログラムの流れは結構複雑です。
    まず最初に list() 関数の再起の流れを理解して下さい。
    次に app() 関数の再起の流れを理解して下さい。
  2. データを入力してソートするプログラムを完成させて下さい。
  3. このプログラムは Binary Tree の典型的なサンプルプログラムです。
  4. Ｃ＃でも同様のプログラム Binary Tree ソート を作成しています。

超初心者のプログラム入門(C/C++)

※・