Binary Tree の基礎

C# で Binary Tree の Object Class を作成します。

Binary Tree の構造

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

/********************************************/
/*★ Binary Tree Object Class     前田 稔 ★*/
/********************************************/
using System;

class console
{
    public static void Main()
    {   Tree    pt = new Tree();
        Tree    wk;

        for(int i=1; i<6; i++)  pt.SetCar(i);
        for(wk=pt.Top; wk!=null; wk=pt.Car(wk))
             Console.WriteLine("{0}",wk.val);
        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;
    }
}

List Object Class には、連鎖(ポインタ)が一個だけ定義されていますが、Binary Tree は Car(前)と Cdr(後)の二個のポインタで連鎖されています。
従って、Binary Tree は List に比べて多様性に富み、プログラムも一段と複雑になります。
class Tree { Tree car; //前のポインタ Tree cdr; //後のポインタ public int val; //データの格納領域

手始めに Car(カー) のポインタだけを使って連鎖してみましょう。
Car だけしか使わないので List Object Class と違いはありません。
先頭から car ポインタをたどり、car の末尾に追加します。

    //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;
    }

【演習】

SetCdr 関数を定義して、Cdr(クダー) のポインタだけを使って連鎖してみて下さい。

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

※・