木構造

木構造、データツリーとは、ある条件を満たした有向グラフである。

概要

有向グラフとは、点（ノード）と方向を持つ辺（ワイヤー）からなる図形である。

木構造とは、有向グラフのうち、最上位の親となる点（ルートノード）が一つに限られ、ループ構造がないようなものである。一つのノードには親ノードが一つだけ存在し、子ノードは0または一つ以上となる。末端のノードをリーフノードと呼ぶ。ルートノードしかない木はルートノード=リーフノードとなる。各リーフにはある値が割り振られる。

パソコンなどのフォルダに格納されているデータは木構造を持つ。hello.exeという実行ファイルの所在地を表すとき、windowなら、C:\Users\niconico\Documents\hello.exe などのようにあらわされる。Cがルートノード、C:\Users\niconico\Documents\までが木構造、リーフノードの値がhello.exe、ということになる。

例

• 住所

領土所属問題は無いものとする。日本では通常、（国→）都道府県→市区町村→番地（→建物名→部屋番号）、という構造を持つ。リーフノードの値は番地、あるいは土地の所有者や居住者など。

国によって下位の構造は異なるが、県→市→県、となるようなこと（ループ構造）や複数の県に属する市などはない。

• 生物の系統樹

ドメイン→界→門→綱→目→科→属→種、という構造を持つ。近縁を表す下位構造として亜門や亜科などを追加することが多い。目以上の分類をぜんぶひっくるめて類と呼ぶことも多い。時代や分類法により変化するが、各基準内部で分類がループすることはない。哺乳類は以下の通り。ここではルートノードは哺乳綱、リーフノードの値は目の名前など。

哺乳綱　┬　単孔類　　　　　　　　　　　　　　　　　　  ┌　ハリネズミ目
　　　　├　有袋類　┬　アメリカ有袋類　　　　　　　　  ├　トガリネズミ目
　　　　│　　　　　└　オーストラリア有袋類　　　　　  ├　コウモリ目
　　　　└　真獣類　┬　アフリカ獣類　　　　　　　　　  ├　鯨偶蹄目
　　　　　 　　　　  ├　異節類　　　　　　　　　　　　  ├　ネコ目（食肉目）
　　　　　   　　　　└　北方真獣類　┬　ローラシア獣類  ┼　ウマ目（奇蹄目）
　　　　　　　　　　　 　 　　　　　 │　　　　 　　　 　└　センザンコウ目
　　　　　　　　　　　 　 　　　　　 └　真主齧類　┬　サル目（霊長目）
　　　　　　　　　　　　　　　　　　 　  　　　　　├　ヒヨケザル目
　　　　　　　　　　　　　　　　　　 　　  　　　　├　ツパイ目　
　　　　　　　　　　　　　　　　　　 　　　  　　　├　ネズミ目（齧歯目）
　　　　　　　　　　　　　　　　　　 　　　　  　　└　ウサギ目

関連項目

• プログラミング関連用語の一覧
• 木
• グラフ