木構造 (データ構造)
もしあれば、左の部分木を間順走査する。 根ノードを調査する。 もしあれば、右の部分木を間順走査する。
多分木では定義されない。2分探索木では、間順走査によって走査する順がソートされた順序になるため、よく使われる。
幅優先探索は、深さが同じノードを浅い方から順に走査していく。
木構造は、一般のグラフ構造と同様の、ノード(節点、頂点)とノード間を結ぶエッジ(枝、辺)あるいはリンクで表すこともできるが、木構造専用の、特に有向の根付き木となるような表現が使われることも多い。
データ構造として使われる木は、ほとんどの場合、根となるノードが決められた根付き木である。さらに、有向木であることも多い。
ノード間の関係は家系図に見立てた用語で表現される。木構造内の各ノードは、0個以上の子ノード (英: child node) を持ち、子ノードは木構造内では下方に存在する(木構造の成長方向は下とするのが一般的である)。子ノードを持つノードは、子ノードから見れば親ノード (英: parent node) である。あるノードから見て、同じ親を持つノードを兄弟ノード (英: sibling node) という。あるノードから見て、その子ノードやそこから先の子ノード全てのいずれかを子孫ノード (英: descendant node) と呼び、その親ノードやそこから先の親ノードの全てのいずれかを先祖ノード (英: ancestor node) と呼ぶ。ノードは高々1個の親ノードを持つ。
根ノード (英: root node) とは、親ノードを持たないノードのこと。根ノードは木構造の最上位にあるノードであり、1つの木構造に高々1つしか存在しない。根ノードからスタートして、親から子へ、またその子へ、とエッジを辿っていくと、あらゆるノードへ必ず到達でき、そのような(根から特定ノードまでの)経路は常に一意である。図で示す場合、根ノードが一番上に描かれるのが普通である。