階層的な関係を表現する際，木構造が使われます。
木構造の各部分は，次のように木と対比できます。

　　�@）根（root）
　　�A）節（node）
　　�B）枝（edge/branch）
　　�C）葉（leaf/terminal node）



木構造は，通常，次のように上下反転した形で図示されます。



ノード間の関係を言い表す際，

　　�@）根に近いノードを親（parent）
　　�A）根から遠いノード／葉を子（child)
　　�B）共通の親を持つ子を兄弟（sibling）

といいます。

いわば，葉は子を持たないノードということができます。

ただし，この分類は，木構造そのものの違いではなく，
あくまで，取り扱い方法によります。

たとえば，以下の木は，順序木とみなせば異なる木であり，
無順序木とみなせば，値が異なるだけの同一の木となります。

　　　　　

左の子（left child）と右の子（right child)の高々２つの子を持つ木を
２分木（binary tree）と呼びます。

ただし，左の子だけのノード，右の子だけのノード，
子を持たないノード（leaf/terminal node）もありえます。

　　　　　

（a）横型探索／幅優先探索（breadth-first search）

ルートに近い点から横方向に探索します。
すなわち，兄弟関係方向を優先して探索する方法です。

以下の木では，以下のような順序で探索します。

　Ａ→Ｂ→Ｇ→Ｃ→Ｄ→Ｈ→Ｋ→Ｅ→Ｆ→Ｉ→Ｊ→Ｌ

　　　　

（ｂ）縦型探索／深さ優先探索（depth-first search）

以下のように，深さ方向を優先して探索する方法です。

　　　　　　
探索する際，たどり着いたノードでチェックや何らかの処理を行います。
この処理を行うタイミングで次のように分類することができます。

　[３三種類のたどり方]

　　�@）行きがけ順（ノード処理　→　左へ　→　右へ）
　　�A）通りがけ順（左へ　→　ノード処理　→　右へ）
　　�B）帰りがけ順（左へ　→　右へ　→　ノード処理）

　　　　　　

例示した２分木では，たどり方によって，
次のように処理順序が異なることになります。

　�@）行きがけ順：Ａ→Ｂ→Ｃ→Ｄ→Ｅ→Ｆ→Ｇ→Ｈ→Ｉ→Ｊ→Ｋ→Ｌ
　�A）通りがけ順：Ｃ→Ｂ→Ｅ→Ｄ→Ｆ→Ａ→Ｉ→Ｈ→Ｊ→Ｇ→Ｌ→Ｋ
　�B）帰りがけ順：Ｃ→Ｅ→Ｆ→Ｄ→Ｂ→Ｉ→Ｊ→Ｈ→Ｌ→Ｋ→Ｇ→Ａ

２分木における処理は，
基本的に，次のような処理分かれます。

　�@）左部分木の処理
　�A）右部分木の処理
　�B）当該ノードの処理



ただし，これらの処理をどの順序で行うかは，
問題が必要とするたどり方によります。

（a）要素データの取り出し

[プログラム処理]

　private ElementData element(long P)
　{
　　　 return DataArea[P].Element;
　}

（b）右ポインタ

[プログラム処理]

　private long right(long P)
　{
　　return DataArea[P].Right;
　}

（c）左ポインタ

[プログラム処理]

　private long left(long P)
　{
　　　return DataArea[P].Left;
　}

（ｄ）要素数のカウント

カウントは，以下のように再帰的な処理になります。
再帰的なアルゴリズムについては５章で説明します。

加算は帰りがけ順になっています。

すなわち，

　　�@）ポインタが空なら０個とする。
　　�A）空でなければ，
　　　　　左部分木のノード数＋右部分木のノー度数＋１

最後の１が当該ノードの数とみなすことができます。


[プログラム処理]

　private long count(long P)
　{
　 　if(P<0) return 0;
　 　return count(left(P))+count(right(P))+1;
　}

（e）木構造すべてを開放

この処理も，再帰的な処理になります。
再帰的なアルゴリズムについては５章で説明します。
１ノードの領域開放は，帰りがけ順になっています。

すなわち，次のように処理します。

　　�@）ポインタが空なら何もしない。
　　�A）空でなければ，
　　　　　・左部分木を開放
　　　　　・右部分木を開放
　　　　　・該当ノードを開放

[プログラム処理]

　private void freeAll(long P)
　{
　　 　if(P<0) return ;
　　　 freeAll(left(P)); freeAll(right(P));
　　　 freeArea(P);
}

（f）木を配列に移動

この処理も，再帰的な処理になります。
再帰的なアルゴリズムについては５章で説明します。
配列への移動は，通りがけ順になっています。

すなわち，次のように処理します。

　　�@）ポインタが空なら何もしない。
　　�A）空でなければ，
　　　　　・左部分木を配列に移動
　　　　　・該当ノードを配列に移動
　　　　　・右部分木を配列に開放

[プログラム処理]

　private long 木を配列に移動(long P, long ID)
　{
　 　 if(P<0) return ID;
　　　long ID1 = 木を配列に移動(left(P), ID);
　　　tempData[ID1].番号 = DataArea[P].Element.番号;
　　　tempData[ID1].氏名 = DataArea[P].Element.氏名;
　 　 tempData[ID1].点数 = DataArea[P].Element.点数;
　 　 ID1++;
　 　 long ID2 = 木を配列に移動(right(P), ID1);
　　　return ID2;
　 }

（ｇ）配列を木に変換

理想的には，左の子孫のノード数と，右の子孫のノード数が等しい場合，
最も効率のよい探索が行われます。

このような木を構成する，最も単純な方法は，
キー順に並べられた配列の真ん中の値をノードとし，
左右に分け，更に左右の配列を木に変換する方法です。

この方法を以下に図示します。
黄色は中央値で，ノードになる要素，
薄青色はＬｅｆｔ，薄赤色はRightになる部分です。



この処理も，再帰的な処理になります。
再帰的なアルゴリズムについては５章で説明します。
ノードの生成は，帰りがけ順になっています。

すなわち，次のように処理します。

　　�@）データがなければ空ポインタを返す。
　　�A）中央より左を左部分木として生成。
　　�B）中央より右を右部分木として生成。
　　�C）中央値のノードを生成し，
　　　　左部分木と右部分木にリンクをはる。

[プログラム処理]

　private long 配列を木に変換(long Left, long Right)
　{
　　if(Right < Left) return -1;
　　long Center = (Left+Right)/2;
　　long PL = 配列を木に変換(Left,Center-1);
　　long PR = 配列を木に変換(Center+1,Right);
　　long P = getArea();
　　if(P < 0) { freeAll(PL); freeAll(PR);}
　 　else
　　{
　　　　DataArea[P].Element.番号 = tempData[Center].番号;
　　　　DataArea[P].Element.氏名 = tempData[Center].氏名;
　　　　DataArea[P].Element.点数 = tempData[Center].点数;
　　　　DataArea[P].Left=PL; DataArea[P].Right=PR;
　　}
　　return P;
　}

（ｈ）木の再構築

木を配列に移動して，開放した後，配列を木に変換します。

[プログラム処理]

　private long 木の再構築(long P)
　{
　　long N = count(P);
　　tempData = new ElementData[N];
　　木を配列に移動(P, 0);
　　freeAll(P);
　　long X = 配列を木に変換(0, N - 1);
　　tempData = new ElementData[0];
　　return X;
　}


（ｉ）番号探索

番号がLeft側にあるかRight側にあるかは
番号の大小比較で分かりますので，全件検索は必要ありません。
このため，効率のよい探索が可能です。

この処理も，再帰的な処理になります。
再帰的なアルゴリズムについては５章で説明します。
判定は，行きがけ順に行います。

　　�@）ポインタが空なら見つからなかったものとする。
　　�A）番号が等しければ，当該ノードを返却。
　　�B）番号が小さければ，左部分木を探索。
　　�C）番号が大きければ，右部分木を探索。

[プログラム処理]

　private long 番号探索(long P,long 番号)
　{
　　　if(P < 0) return -1;
　　　ElementData E = element(P);
　　　if(番号 == E.番号) return P;
　　　else if(番号 < E.番号) return 番号探索(left(P),番号);
　　　else return 番号探索(right(P),番号);
　}


（ｊ）キーでないデータの探索

キーでないデータを探索するには，
そのデータがLeft側にあるかRight側にあるかが
分かりませんので，
全件探索を行う必要があります。

すなわち，
当該ノードであれば，探索終わり。
当該ノードでなければ，
左側を探索し，あれば探索終わり。
なければ右側を探索します。

この処理も，再帰的な処理になります。
再帰的なアルゴリズムについては５章で説明します。
判定は，行きがけ順に行います。

例として，氏名を探索する例を示します。

[プログラム処理]

　private long 氏名探索(long P,string 氏名)
　{
　　　if(P < 0) return -1;
　　　ElementData E = element(P);
　　　if(string.Compare(氏名,E.氏名) == 0) return P;
　　　long PL = 氏名探索(left(P),氏名);
　　　if( PL >= 0) return PL;
　　　return 氏名探索(right(P),氏名);
　}


横型探索の場合，
訪問すべきノード番号を入れる表を用意し，
訪問したノードが探索対象でない場合，
そのノードのLeft，Ｒｉｇｈｔのポインタを保管しておきます。

　　　　　　　　　
探索の手順は，以下のようになります。

　　(a) N=0，I = 0，訪問ノード表[N++]=ルートとする。

　　(b) I < Nの間，以下を繰り返す。

　　　　(b-1) 訪問ノード表[I]が探索すべきノードのとき検索終わり。
　　　　(b-2) leftが空でなければ，leftを訪問ノード表に追加。
　　　　　　　　（追加したとき，Ｎカウントアップ）
　　　　(b-3) rightが空でなければ，rightを訪問ノード表に追加。
　　　　　　　　（追加したとき，Ｎカウントアップ）
　　　　(b-4) Iをカウントアップ。

　　　　　　　（訪問ノード表の動き）
　　　　　　

　private long 横型探索(long P,string 氏名)
　{
　　　long PP, PX; long Num=count(P);
　　　long [] P_Array=new long[Num];
　　　N=0:P_Array[N++]=P; int i=0;
　　　while (i < N)
　　　{
　　　　　PP=P_Array[i];
　　　　　ElementData E=element(PP);
　　　　　if(string.Compare(氏名,E.氏名) == 0) return PP;
　　　　　PX=left(PP) ;if(PX>=0) P_Array[N++]=PX;
　　　　　PX=right(PP);if(PX>=0) P_Array[N++]=PX;
　　　　　i++;
　　　}
　}

ところで，すでに探索したノードは保管する必要がありません。
領域がもったいないようであれば，待ち行列として実装します。

　　　

　private void Enque(long V,ref int N, ref long[] PA)
　{ PA[N]=V; N++; }

　private long Deque(ref int N,ref long[] PA)
　{ 　long R=PA[0];N--; for(int k=0;k<N;k++)PA[k]=PA[k+1]; return R; }

　private long 横型探索(long P,string 氏名)
　{
　　　long PP,PX;string S; long Num=count(P);
　　　long [] P_Array=new long[Num];
　　　int N=0;Enque(P,ref N,ref P_Array); int i=0;
　　　while (N>0)
　　　{
　　　　　　PP=Deque(ref N,ref P_Array);
　　　　　　ElementData E=element(PP);
　　　　　　if(string.Compare(氏名,E.氏名) == 0) return PP;
　　　　　　PX=left(PP);if(PX>=0) Enque(PX,ref N,ref P_Array);
　　　　　　PX=right(PP);if(PX>=0) Enque(PX,ref N,ref P_Array);
　　　}
　　　return -1;
}

［Program 3−7］
　　

1. 基本的なアルゴリズム

2. 基本的なデータ構造

3. 操作を伴うデータ構造

4. 探索

5. 再帰的アルゴリズム

6. ソート

7. 集合

8. 文字列処理

9. 色々なアルゴリズム


上のタイトルをクリックします