TreeEdit

ツリーは、次の同等の条件のいずれかを満たす無向グラフGです。

• Gは連結で非巡回（サイクルを含まない）です。
• Gは非巡回であり、gにエッジが追加されると単純なサイクルが形成されます。
• Gは接続されていますが、gから単一のエッジが削除されると切断されます。
• Gは接続されており、3つの頂点完全グラフK3はGのマイナーではありません。
• Gの任意の二つの頂点は、一意の単純なパスで接続することができます。

Gが有限個の頂点を持ち、それらのうちのnを言う場合、上記の文は次の条件のいずれかにも相当します。

• Gは接続され、n−1の辺を持
• Gは連結であり、Gのすべての部分グラフは、0または1つの入射辺を持つ少なくとも1つの頂点を含む。 （つまり、Gは連結で1-縮退である。)
• Gは単純なサイクルを持たず、n−1のエッジを持ちます。グラフ理論の他の部分と同様に、次数ゼログラフ（頂点のないグラフ）は一般に木ではないと見なされます。

グラフ理論の他の部分と同様に、次数ゼログラフ（頂点のないグラフ）は一般に木であるとはみなされません。: グラフとして空連結であるが（任意の2つの頂点はパスで連結できる）、代数的位相幾何学では空でない木とは異なり0-連結ではなく（あるいは(-1)-連結でさえもない）、”辺よりも1つ以上の頂点”関係に違反する。 しかし、それはゼロの木からなる森林とみなされるかもしれません。

内部頂点（または内部頂点または分岐頂点）は、次数が2以上の頂点です。

内部頂点（または内部頂点または分岐頂点）は、次数が2以上の頂点 同様に、外部頂点（または外部頂点、終端頂点、または葉）は次数1の頂点です。

既約木（またはシリーズ縮小木）は、次数2の頂点が存在しない木です（OEISのシーケンスA000014で列挙されています）。

ForestEdit

フォレストは、任意の二つの頂点が最大で一つのパスで接続されている無向グラフです。 同様に、森林は無向非巡回グラフであり、そのすべての連結成分は木である。 特別な場合として、次数ゼログラフ（ゼロの木からなる森林）、単一の木、およびエッジのないグラフは、森林の例です。すべてのツリー V−E=1であるため、合計頂点と合計エッジの差を差し引くことで、フォレスト内にあるツリーの数を簡単に数えることができます。 TV-TE=森の中の木の数。p>

PolytreeEdit

polytree（または有向木または有向木または単連結ネットワーク）は、基になる無向グラフが木である有向非巡回グラフ（DAG）です。 言い換えれば、有向辺を無向辺に置き換えると、接続されていて非循環の両方の無向グラフが得られます。

いくつかの著者は、”有向木”という句を、エッジがすべて特定の頂点に向けられている場合、またはすべてが特定の頂点から離れている場合に制限しています（arborescenceを参照）。

PolyforestEdit

polyforest(または有向フォレストまたは有向フォレスト)は、基になる無向グラフがフォレストである有向非巡回グラフです。 言い換えれば、有向辺を無向辺に置き換えると、非循環である無向グラフが得られます。

いくつかの著者は、”有向森林”という句を、各連結成分の辺がすべて特定の頂点に向けられている場合、またはすべてが特定の頂点から離れて向けられている場合に制限している（分岐を参照）。

ルート化されたtreeEdit

ルート化されたツリーは、1つの頂点がルートに指定されたツリーです。 ルート化されたツリーのエッジには、ルートから離れているかルートに向かっているかの自然な向きを割り当てることができ、その場合、構造は有向ルート化されたツリーになります。 有向根ざした木は、ルートから離れた向きを持っている場合、それはarborescenceまたはout-treeと呼ばれ、それはルートに向かって向きを持っている場合、それはanti-arborescenceまたはin-treeと呼ばれています。 あるグラフGの部分グラフである根付き木Tは、GのすべてのT-パスの端がこの木順序で比較可能である場合にのみ、通常の木である(Diestel2005,p.15)。 ルート化されたツリーは、各頂点での近傍の順序付けなどの追加構造を持つことが多いが、コンピュータサイエンスにおける重要なデータ構造である。

木が根を持つことになっている文脈では、指定された根のない木は自由木と呼ばれます。

ラベル付けされたツリーは、各頂点に一意のラベルが与えられたツリーです。 N個の頂点上のラベル付きツリーの頂点には、通常、ラベル1、2、が与えられます。.. 再帰ツリーは、頂点ラベルがツリーの順序を尊重するラベル付きルートツリーです（つまり、 2つの頂点uとvに対してu<vの場合、uのラベルはvのラベルよりも小さくなります）。

ルート化されたツリーでは、頂点vの親はルートへのパス上のvに接続された頂点であり、すべての頂点は親を持たないルートを除いて一意の親を持 頂点vの子は、vが親である頂点です。 頂点vのアセンダントは、vの親であるか、vの親のアセンダントである（再帰的に）任意の頂点です。 頂点vの子孫は、vの子であるか、vの子のいずれかの子孫である（再帰的に）任意の頂点です。vへの兄弟は、vと同じ親を持つツリー上の他の頂点です。leafは子のない頂点です。 内部頂点とは、リーフではない頂点のことです。

ルート化されたツリー内の頂点の高さは、その頂点から葉までの最長の下向きのパスの長さです。

ルート化されたツリー内の頂点の高さは、その頂点 木の高さは根の高さです。 頂点の深さは、そのルート（ルートパス）へのパスの長さです。 これは、一般的に、様々な自己均衡木、特にAVL木の操作に必要とされる。 根は深さゼロ、葉は高さゼロ、そして単一の頂点だけを持つ木（したがって根と葉の両方）は深さと高さゼロを持っています。 従来、空の木（頂点が許可されている場合は頂点のない木）は深さと高さ-1を持ちます。

k-aryツリーは、各頂点が最大k個の子を持つ根付きツリーです。 2-aryの木はしばしば二分木と呼ばれ、3-aryの木は時には三分木と呼ばれます。

Ordered treeEdit

ordered tree(またはplane tree)は、各頂点の子に対して順序が指定されたルート化されたツリーです。 これは、子の順序付けは、ルートが頂点にあり、各頂点の子がその頂点よりも低い平面内の木の埋め込みと同等であるため、”平面木”と呼ばれます。 平面内に根を持つ木を埋め込むと、子の方向を左から右に固定すると、埋め込みは子の順序を与えます。 逆に、順序付けられた木が与えられ、通常は上に根を描くと、順序付けられた木の子頂点を左から右に描くことができ、本質的にユニークな平面埋め込みが得られます。