Binary Tree Sort new

Binary Tree Sort で new を使ってセルを割り当てます。
セルを再起的に解放する関数や検索する関数も紹介します。

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

プログラムの説明

  1. ソースプログラムです。
    List 構造の基礎は List 連鎖の基礎 を参照して下さい。
    ファイル名 説明
    Treenew.cpp Binary Tree Sort new
  2. Binary Tree Sort の説明は Binary Tree ソート を参照して下さい。
    TREE がセルを格納する構造体です。
    *PT が Binary Tree へのメインポインタです。
    List の連鎖には、後ろに連鎖して行く方法と、前に連鎖していく方法があります。
    今回は List の前に連鎖して行くので、*PT は最後に格納したセルをポイントしています。
    前に連鎖するとスマートなプログラムになるのですが、少し解り難いかも知れません。 (^_^;)
    *WP は作業用のポインタです。
    t[] がソート前のデータが格納されている配列です。
        struct  TREE
        {   struct  TREE    *car;
            struct  TREE    *cdr;
            int     v;
        };
    
        struct  TREE    *PT;
        struct  TREE    *WP;
        int             t[] = { 7, 2, 10, 5, 3, 6, 9, 1, 4, 8 };
        
  3. main() 関数です。
    sort(t,10); で t[] に格納されている10件のデータを TREE に格納します。
    list(PT); で昇順に印字します。
    WP= Serch(PT,3); でデータ3を検索してみました。
    Free(PT); で全てのセルを解放します。
        //☆ MAIN
        int  main()
        {
            sort(t,10);
            printf("\n昇順に SORT した結果は次の通りです\n");
            list(PT);
            // 番号で検索します
            WP= Serch(PT,3);
            if (WP!=NULL)   printf("%d\n", WP->v);
            Free(PT);
            _getch();
            return 0;
        }
        
  4. TREE を構築する sort() 関数です。
    new TREE; でセルを割り当ててデータを格納します。
    app(&PT,WP); で一個のセルを連鎖する関数を呼び出します。
        // TREE(セル)を一個割り当てて t[n] の値を格納する
        void  sort(int t[], int n)
        {   int     i;
    
            PT= NULL;
            for(i=0; i<n; i++)
            {   WP= new TREE;
                WP->car=WP->cdr= NULL;
                WP->v= t[i];
                app(&PT,WP);
            }
        }
        
  5. 一個のセルを連鎖する app() 関数です。
    **pt はセルを連鎖する car や cdr のポインタです。
    *pt が NULL のとき(連鎖されていないとき)は、新しいセル(*w) を連鎖します。
    *pt が連鎖されているときは、v の大小関係で car または cdr をたどります。
        // Binary Tree に TREE を一件追加登録
        void  app(struct TREE **pt, struct TREE *w)
        {
            if (*pt==NULL)      {   *pt= w;  return;  }
            // v の大小関係で car, cdr に振り分ける
            if ((*pt)->v > w->v)    app(&(*pt)->car,w);
            else                    app(&(*pt)->cdr,w);
        }
        
  6. Binary Tree を昇順に表示する list() 関数です。
    最初 *pt にはメインポインタ(*PT)が渡されます。
    連鎖の終端まで car をたどって list() を再起コールします。
    終端に達すると pt->v の値を印字します。
    次に連鎖の終端まで cdr をたどって list() を再起コールします。
        // 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);
        }
        
  7. num が格納されているセルを検索する Serch() 関数です。
    pt==NULL のときは num が見つからなかったときです。
    num を見つけたときは、そのときの pt を return します。
    一致しないときは car をたどって再起コールします。
    car に見つからなかったときは cdr をたどって再起コールします。
        // num で検索する
        TREE  *Serch(TREE *pt, int num)
        {   struct  TREE    *WK;
            if (pt==NULL)   return NULL;
            if (pt->v==num) return pt;
            WK= Serch(pt->car, num);
            if (WK!=NULL)   return WK;
            return Serch(pt->cdr, num);
        }
        
  8. List をたどって全ての領域を解放する Free() 関数です。
    new で割り当てた領域は delete で解放しなければなりません。
    printf("%3d 開放",pt->v); のコメントを外すと解放した領域の num を印字するので、確認して下さい。
        // 再帰で領域を開放する
        void  Free(TREE *pt)
        {   if (pt==NULL)   return;
            Free(pt->car);
            Free(pt->cdr);
            //printf("%3d 開放",pt->v);
            delete pt;
            return;
        }
        
  9. ソースコードは極めてシンプルですがプログラムの流れは結構複雑です。
    この手のプログラムは眺めていただけでは理解できません。 (^_^;)
    ソースコードを色々さわって試してみて下さい。

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