木構造 (データ構造)
アイテム(データを持つノード)数を数え上げる。
あるアイテムを探索する。
新たなアイテムを木構造の特定の位置に追加する。
アイテムを削除する。
部分木を削除する(枝刈り)
部分木を追加する(接ぎ木)
任意のノードから根ノードを探す。
二分ヒープなどの木構造では、根ノードは特別な属性を持つ。木構造内の全てのノードは、そのノードを頂点とする部分木の根ノードと見なすことができる。
葉ノード (英: leaf node) とは、子ノードを持たないノードのこと。葉ノードは木構造の下位の末端にあるノードであり、ひとつの木に複数存在しうる。
内部ノード (英: internal node、inner node) とは、子ノードを持つノード、すなわち葉ノード以外のノードのこと。
高さ (英: height) とは、あるノードについて、そのノードからその子孫である葉ノードへのエッジ数の最大値のこと。 根ノードの高さはその木構造の高さである。
深さ (英: depth) とは、逆に、あるノードについて、そのノードから根ノードまでのエッジ数のこと。根ノードの深さは 0 である。
部分木 (英: subtree) は、木構造の一部であり、それ自身も完全な木構造となっている部分を指す。木構造 T の任意のノードは、その配下の全ノードと共に T の部分木を構成する。根ノードを頂点とする部分木は、その木構造全体と等しい。根ノード以外を頂点とする部分木は真部分木 (英: proper subtree) と呼ばれる(部分集合と真部分集合とのアナロジー)。
森 (英: forest) とは、木の集合のこと。グラフ理論では、森は閉路をもたない(連結とは限らない)グラフである。 森が順序木の順序集合である場合、これを木の木と考えることで前順、間順、後順の走査法を再帰的に定義できる。