■トゥリー(樹木構造)■

↑

■トゥリー(樹木構造)■


リストとトゥリー

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

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

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

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

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

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

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


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

【Cコーディング例】二分木

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 = (KSTNODE*)malloc(ksaloc * sizeof(KSTNODE));

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

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


(C)copyright ffortune.net 1995-2016 produced by ffortune and Lumi.
お問い合わせはこちらから