1件
木構造、データツリーとは、ある条件を満たした有向グラフである。
概要
有向グラフとは、点（ノード）と方向を持つ辺（ワイヤー）からなる図形である。
木構造とは、有向グラフのうち、最上位の親となる点（ルートノード）が一つに限られ、ループ構造がないようなものである。一つのノードには親ノードが一つだけ存在し、子ノードは0または一つ以上となる。末端のノードをリーフノードと呼ぶ。ルートノードしかない木はルートノード=リーフノードとなる。各リーフにはある値が割り振られる。
パソコンなどのフォルダに格納されているデータは木構造を持つ。hello.exeという実行ファイルの所在地を表すとき、windowなら、C:\Users\niconico\Documents\hello.exe などのようにあらわされる。Cがルートノード、C:\Users\niconico\Documents\までが木構造、リーフノードの値がhello.exe、ということになる。
例
領土所属問題は無いものとする。日本では通常、（国→）都道府県→市区町村→番地（→建物名→部屋番号）、という構造を持つ。リーフノードの値は番地、あるいは土地の所有者や居住者など。
国によって下位の構造は異なるが、県→市→県、となるようなこと（ループ構造）や複数の県に属する市などはない。
ドメイン→界→門→綱→目→科→属→種、という構造を持つ。近縁を表す下位構造として亜門や亜科などを追加することが多い。目以上の分類をぜんぶひっくるめて類と呼ぶことも多い。時代や分類法により変化するが、各基準内部で分類がループすることはない。哺乳類は以下の通り。ここではルートノードは哺乳綱、リーフノードの値は目の名前など。
哺乳綱 ┬ 単孔類 ┌ ハリネズミ目
├ 有袋類 ┬ アメリカ有袋類 ├ トガリネズミ目
│ └ オーストラリア有袋類 ├ コウモリ目
└ 真獣類 ┬ アフリカ獣類 ├ 鯨偶蹄目
├ 異節類 ├ ネコ目（食肉目）
└ 北方真獣類 ┬ ローラシア獣類 ┼ ウマ目（奇蹄目）
│ └ センザンコウ目
└ 真主齧類 ┬ サル目（霊長目）
├ ヒヨケザル目
├ ツパイ目
├ ネズミ目（齧歯目）
└ ウサギ目
関連項目
- 0
- 0pt
