テクノロジー編25: データ構造

データの階層的な関係を表すのに便利なデータ構造。
「節点」が、親子関係を持ちながらつながっているような構造。
一般的に、より上位の節点を上に、より下位の節点を下に配置して表現する。
ファイルシステムや構文解析などで利用される。

場合によっては同じ意味でも異なる用語が使われることがある。

【枝】
節点同士をつなぐ線のこと。

【親子】
枝によってつながれている節点同士の関係を「親子関係」と呼ぶ。
枝でつながれている節点のうち、上位の節点が「親」、下位の節点が「子」。

【兄弟】
同じ親を持つ節点同士。

【祖先】
ある節点から見たときに、親、親の親、親の親の親、... のように表せる節点。

【子孫】
ある節点から見たときに、子、子の子、子の子の子、... のように表せる節点。

【根】
親を持たない、最上位の節点。
根以外の節点は、必ず 1 個の親を持つ。

【葉】
子を持たない節点。
葉以外の節点は、必ず 1 個以上の子を持つ。

【深さ】
その節点から根までの距離。
一般的には根の深さを 0 とする。

その木全体における深さの最大値を、「木の深さ」という。

【部分木】
その節点を根とし、その節点と子孫からなる木のこと。
親子関係はもとの木からそのまま引き継がれる。