※有料会員になるとこの動画をご利用いただけます
詳しい説明を読む
#05:木構造の基本用語
このチャプターでは、木構造の基本用語を学習します。
データの階層的な関係を表すのに便利なデータ構造。
「節点」が、親子関係を持ちながらつながっているような構造。
一般的に、より上位の節点を上に、より下位の節点を下に配置して表現する。
ファイルシステムや構文解析などで利用される。
場合によっては同じ意味でも異なる用語が使われることがある。
【枝】
節点同士をつなぐ線のこと。
【親子】
枝によってつながれている節点同士の関係を「親子関係」と呼ぶ。
枝でつながれている節点のうち、上位の節点が「親」、下位の節点が「子」。
【兄弟】
同じ親を持つ節点同士。
【祖先】
ある節点から見たときに、親、親の親、親の親の親、... のように表せる節点。
【子孫】
ある節点から見たときに、子、子の子、子の子の子、... のように表せる節点。
【根】
親を持たない、最上位の節点。
根以外の節点は、必ず 1 個の親を持つ。
【葉】
子を持たない節点。
葉以外の節点は、必ず 1 個以上の子を持つ。
【深さ】
その節点から根までの距離。
一般的には根の深さを 0 とする。
その木全体における深さの最大値を、「木の深さ」という。
【部分木】
その節点を根とし、その節点と子孫からなる木のこと。
親子関係はもとの木からそのまま引き継がれる。