木構造
木構造とは、階層的な構造を表すのに適したデータ構造です。ソフトウェア開発ではドキュメント、組織図、グラフィックスなど階層構造を抽象化する方法として活用されます。
また、木構造は、効率的なアルゴリズムとデータ構造を実装するための基礎構造で、情報処理とプログラミングには欠かせない概念となります。標準ライブラリとして提供されている多くのアルゴリズムやデータ構造が木構造に関連しています。
根付き木
木構造とは節点（node)と節点同士を結ぶ辺(edge)で表されるデータ構造です。
根付き木の節点には親子関係があります。根付き木Tの根rから節点xに至る経路上の最後の辺が節点pと節点xを繋ぐとき、 p を x の親(parent)、xをpの子(child)と呼びます。
根は親を持たない唯一の節点です。子を持たない節点は外部節点(external node)または葉(leaf)と呼ばれます葉でない節点を内部節点(internal node)と呼びます。
根付きの木Tの節点xの子の数をxの次数(degree)と呼びます。
根rから節点x までの距離の長さをxの深さ(depth)と呼びます。また、節点xから葉までの経路の長さの最大値を設定xの高さ(height)と呼びます。根の高さが最も高くなり、それを木の高さと呼びます。
用語
- node 節点
- edge 辺
- parent 親
- child 子
- leaf (external node) 葉(外部節点)
- internal node 内部節点
- degree 任意の節点の子の数、次数（孫は数えない）
- depth 根から任意の節点までの経路の長さ、深さ
- height 任意の節点から葉までの経路の長さの最大値、高さ
二分木
一つの根を持ち、すべての節点についてその子の数が2以下である木を根付き2分木と言います。
二分木では節点が持つ子の数が2以下となりますが、左の子と右の子は区別されます。つまり、子が一つの場合それが左の子なのか、右の子なのかが厳密に区別されます。