トゥリー

※「セキュリティ保護のため...」というメッセージが出る方・日本語が入力できない方へ
 ■トゥリー(樹木構造)■

リストとトゥリー

リストの場合はデータが横１列に並んでおり、各データには「前のデータ」と「後ろのデータ」がある。

これに対して、トゥリーというのは、１個のデータ（根,root）から枝分かれしていき、各データにちょうど１個の親(parent)と複数の子供(child)があるようなデータ構造を言う。（ただし根だけは親を持たない）

★トゥリー構造において、

(1)出発点になっているデータを根（root）と呼ぶ。普通トゥリーは根を一番上に書く。

(2)直接線でつながっているデータは親子関係にあるという。トゥリーにおいて根以外のデータは唯一つの親を持つ。各データの子供が２個以下のトゥリーは特に二分木（Binary Tree）と呼ばれる。

(3)親と子をつなぐ線を枝（edge）と呼ぶ。又、各データを節（node）と呼ぶ。

(4)一番下位のデータ、つまり子供を持たないデータを葉（Leaf）と呼ぶ。

トゥリー構造をコンピュータ上で実現する場合、リストと同様にポインターを用いることが多い。（用いない方法もある。）

【Ｃコーディング例】二分木
   typedef struct {
       long   code;
       char*  name;
   } KST;
   typedef struc {
       KST    kst;
       int    parent;
       int    child1;
       int    child2;
   } KSTNODE;
   
   int kscnt;
   int ksaloc;
   KSTNODE* ks;
   char* ksbuf;
   ----------------------
   ksaloc = KSALOCFIRST;
   ksbuf = (char*)malloc(KSBUFFIRST);
   ks = (KSNODE*)malloc(ksaloc * sizeof(KST));

★特殊な名称を持つトゥリー

探索木（Search Tree ）: 二分木の一種で親と二人の子供の値を比較した時、必ず、左の子供　＜　親　＜　右の子供　となっている物。大量のデータを分類するのに使用する。探索木の上で値の小さい順にデータをたどることをTree Walkingと言う。
ヒープ・トゥリー（Heap Tree ）: 二分木の一種で親データの値が必ず子供の値より大きい（小さい）トゥリー。ヒープソートという高速ソートに使用される。このトゥリーは普通ポインターを使わずに管理される。（詳細はその内ソートの解説のところで書きます）
Ｂトゥリー（B Tree）: 各節において、子供の値は左から順に小さいように並んでいて、親の値は一番右側の子供の値（つまり最大値）と一致するようになっているトゥリーを言う。古いｉＳＡＭ・ＶＳＡＭファイルに代わる索引管理方法として、1970年代から普及してきた。データベースの索引としてよく使われる。