697.txt

[1] [DFN[[RUBY[木構造][きこうぞう]@en[tree structure]]]]、あるいは単に[DFN[[RUBY[木][き]@en[tree]]]]は、
[[計算機]]の世界で非常によく用いられる[[データ構造]]です。[[木]]は[[グラフ]]の[[部分集合]]であって、
[[閉路]]を持たないものです。

[2] [[グラフ]]に[[有向]]・[[無向]]の概念があるのと同様、[[木]]についても[[有向木]]、
[[無向木]]を考えることもあります。とはいえほとんどすべての場合に[[親子]]関係 ([[親]]→[[子]]という向き)
を考えるので、実質的に[[木]]といえば[[有向木]]になっています。

* 木の部分

[4] 
[FIG(short list)[
- [[枝]]
- [[節点]]
-- [[根]]
-- [[葉]]
- [[部分木]]
]FIG]

[5] [[節点]]の[[関係]]:
[FIG(short list)[
- [[包括的子孫]]
-- [[子孫]]
--- [[子][子節点]]
- [[包括的祖先]]
-- [[祖先]]
--- [[親][親節点]]
- [[兄妹]]
]FIG]

[6] [[順序]]・[[探索]]:
[FIG(short list)[
- [[木順]]
- [[深さ優先探索]]
- [[幅優先探索]]
- [[行きがけ順]]
- [[通りがけ順]]
- [[帰りがけ順]]
]FIG]

* 色々な木

[3] [[木]]は色々なところで使われています。

[FIG(short list)[
- [[節点木]]
-- [[文書木 (DOM)]]
-- [[影木]]
- [[内容木]]
- [[文書木 (CSS)]]
- [[木 (IETF)]]
- [[二分木]]
- [[赤黒木]]
]FIG]