樹（tree）可以用幾種方式定義。定義樹的一種自然的方式是遞歸方法。一棵樹是一些節(jié)點(diǎn)的集合。這個集合可以是空集；若非空，則一棵樹由稱作根（root）的節(jié)點(diǎn) r 以及 0 個或多個非空的（子）樹 組成，這些子樹中每一棵的根都被來自根 r 的一條有向的邊（edge）所連接。

每一棵子樹的根叫做根 r 的兒子（child），而 r 是每一棵子樹的根的父親（parent）。

從遞歸定義中我們發(fā)現(xiàn)，一顆樹是 N 個節(jié)點(diǎn)和 N-1 條邊的結(jié)合，其中的一個節(jié)點(diǎn)叫作根。存在 N-1 條邊的結(jié)論是由下面的事實(shí)得出的，每條邊都將某個點(diǎn)連接到它的父親，而除去根節(jié)點(diǎn)外每一個節(jié)點(diǎn)都有一個父親。

沒有兒子的節(jié)點(diǎn)稱為樹葉（leaf）；具有相同父親的節(jié)點(diǎn)為兄弟（sibling）；用類似的方法可以定義祖父（grandparent）和孫子（grandchild）關(guān)系。

從節(jié)點(diǎn) 到 的路徑（path）定義為節(jié)點(diǎn) 的一個序列，使得對于 1 ≤ i < k，節(jié)點(diǎn) 是 的父親。這個路徑的長（length）為該路徑上邊的條數(shù)，即 k-1.從每一個節(jié)點(diǎn)到它自己有一條長為 0 的路徑。注意，在一棵樹中從根到每個節(jié)點(diǎn)恰好存在一條路徑。

對任意節(jié)點(diǎn) 的深度（depth）為從根到 的唯一路徑的長。因此，根的深度為 0。 的高（height）是從 到一片樹葉的最長路徑的長。因此所有的樹葉的高都是 0。一棵樹的高等于它的根的高。一棵樹的深度等于它的最深的樹葉的深度；該深度總是等于這棵樹的高。

如果存在從 到 的一條路徑，那么 是 的一位祖先（ancestor）而 是 的一個后裔（descendant）。如果 ≠ ，那么 是 的一位真祖先（proper ancestor）而 是 的一個真后裔（proper descendant）。