树(tree)是n(n≥0)个结点的有限集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或简称为树根。树的递归定义如下：

（1）单个结点是一棵树，树根就是该结点本身。

（2）设T1,T2,..,Tk是K棵树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父结点，则得到一棵新树，结点n就是新树的根，称n1,n2,..,nk为一组兄弟结点，它们都是结点n的儿子结点。T1,T2,…,Tk为结点n的k个子树。

（3）空集合也是树，称为空树。空树中没有结点，当然也没有关系。

下面是树的基本术语：

（1）结点的度。结点的子树的个数。图6.1中结点A的度为3；结点B的度为2；结点M的度为0。

（2）叶子。度为0的结点，也称为终端结点。

（3）分支结点。度不为0的结点，也称为非终端结点。

（4）树的度。树中结点的度的最大值。

（5）层次、树的深度。根为第1层，根的孩子为第2层…。层次的最大值称为树的深度。

（6）孩子、双亲。结点的子树的根称为孩子；这个结点称为孩子的双亲。

（7）兄弟、堂兄弟。有相同双亲的结点互称为兄弟；同一层上不同双亲的结点互称为堂兄弟。

（8）子孙、祖先。结点的直接后继和间接后继称为结点的子孙；从根到该结点的分支上的所有结点称为该结点的祖先。

（9）有序树。各子树的顺序不能改变的树。

（10）森林。m(m≥0)棵互不相交的树的集合。