Binary Tree ソート

20
32
34
69
71
73
74
78
78

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

プログラムの説明

1. フォルダーに次のファイルを格納して下さい。
   

   /********************************************/ /*★ Binary Tree Object Class 前田 稔 ★*/ /********************************************/ using System; class console { public static void Main() { Tree pt = new Tree(); Random rand = new Random(); for(int i=1; i<10; i++) pt.App(rand.Next(100)); pt.Print(pt.Top); System.Console.ReadLine(); } } class Tree { Tree car; //前のポインタ Tree cdr; //後のポインタ public int val; //データの格納領域 Tree top; //Binary Tree のトップポインタ //Constructor public Tree() { car = null; cdr = null; top = null; } //top を取得 public Tree Top { get { return top; } } //pt の car を取得 public Tree Car(Tree pt) { if (pt==null) return null; return pt.car; } //pt の cdr を取得 public Tree Cdr(Tree pt) { if (pt==null) return null; return pt.cdr; } //car の末端にセット public void SetCar(int v) { Tree wk; Tree wp; wk= new Tree(); wk.val= v; if (top==null) { top= wk; return; } for(wp=top; wp.car!=null; wp=wp.car); wp.car= wk; return; } //cdr の末端にセット public void SetCdr(int v) { Tree wk; Tree wp; wk= new Tree(); wk.val= v; if (top==null) { top= wk; return; } for(wp=top; wp.cdr!=null; wp=wp.cdr); wp.cdr= wk; return; } //Binary Tree を表示 public void Print(Tree pt) { if (pt==null) return; if (pt.car!=null) Print(pt.car); Console.WriteLine("{0} ",pt.val); if (pt.cdr!=null) Print(pt.cdr); } //car と cdr に振り分けて登録 public void App(int v) { Tree wk; wk= new Tree(); wk.val= v; if (top==null) { top= wk; return; } app(top,wk); } //Binary Tree に TREE を一件追加登録 void app(Tree pt, Tree wk) { if (pt.val > wk.val) { if (pt.car==null) { pt.car= wk; return; } app(pt.car,wk); return; } else { if (pt.cdr==null) { pt.cdr= wk; return; } app(pt.cdr,wk); return; } } }

2. Binary Tree 構造とはセルから二個のポインタで次のセルを連鎖したデータ構造です。
   セルは次のセルに連鎖するための car と cdr のポインタとデータ領域で構成されます。
   最も単純なセルは次のようになります。
   

   carポインタ

   cdrポインタ

   データ

3. Binary Tree ソートでは car には自分より小さいデータを格納したセルへのポインタを格納します。
   cdr には自分より大きいデータを格納したセルへのポインタを格納します。
   val にはソートするデータを格納します。
   top は Binary Tree の先頭セルへのポインタです。
   

   Tree car; //前のポインタ Tree cdr; //後のポインタ public int val; //データの格納領域 Tree top; //Binary Tree のトップポインタ

4. Main 関数の説明です。
   最初に new Tree(); で Binary Tree Class を生成します。
   乱数で１０件のデータを発生させて pt.App で Binary Tree に登録します。
   登録したデータを pt.Print で昇順に印字します。
   

   public static void Main() { Tree pt = new Tree(); Random rand = new Random(); for(int i=1; i<10; i++) pt.App(rand.Next(100)); pt.Print(pt.Top); System.Console.ReadLine(); }

5. Binary Tree にデータを追加する App 関数です。
   new で新しいセルを割り当てて car と cdr に振り分けて登録します。
   top が null のとき(最初のデータ)は top から連鎖します。
   二件目以降のデータは app 関数で car と cdr に振り分けます。
   App 関数と app 関数を使っていますが、大文字／小文字の違いがあるし、パラメータも異なっているので別の関数です。
   

   //car と cdr に振り分けて登録 public void App(int v) { Tree wk; wk= new Tree(); wk.val= v; if (top==null) { top= wk; return; } app(top,wk); }

6. app 関数では pt と wk のデータの値を比べて pt の方が大きいときは car に、そうで無いときは cdr に登録します。
   car または cdr から連鎖されているときは、次のセルを調べるために app 自身を再起コールします。
   

   //Binary Tree に TREE を一件追加登録 void app(Tree pt, Tree wk) { if (pt.val > wk.val) { if (pt.car==null) { pt.car= wk; return; } app(pt.car,wk); return; } else { if (pt.cdr==null) { pt.cdr= wk; return; } app(pt.cdr,wk); return; } }

7. 数件のデータが格納された状態を画像で示します。
   
   
   
   1. 最初に２が登録されます。
      
   2. 次の１は２より小さいので car から連鎖されます。
      
   3. ４は２より大きいので cdr から連鎖されます。
      
   4. ３は２より大きいので cdr を参照しますが４が連鎖されています。
      そこで４のセルと比較して４より小さいので car から連鎖します。
      
   5. ５は２より大きいので cdr を参照しますが４が連鎖されています。
      そこで４のセルと比較して４より大きいので cdr から連鎖します。
      
8. Print 関数は Main から pt.Print(pt.Top); で呼び出されます。
   Top から car と cdr で連鎖されている全てのセルをたどり印字しているのですが驚くほどスマートでしょう。
   しかもデータは昇順にソートして印字されます。
   

   //Binary Tree を表示 public void Print(Tree pt) { if (pt==null) return; if (pt.car!=null) Print(pt.car); Console.WriteLine("{0} ",pt.val); if (pt.cdr!=null) Print(pt.cdr); }

9. C/C++ でも同様のプログラム Binary Tree ソート を作成しています。
   セルを再起的に解放する関数や検索する関数は「超初心者のプログラム入門(C/C++)」から 「Binary Tree Sort new」を参照して下さい。
   

【演習】

1. Print 関数の全てのセルをたどるロジックを検証して下さい。
   
2. 降順にソートして印字して下さい。
   

超初心者のプログラム入門(C# Frame Work)