1. 树

树是一个或多个节点的有限集合T，使得：

a）有一个特别指定的节点，叫做树的根root(T)；以及：

b）剩余的节点（排除根）被分划$m \geq 0$个不相交的集合$T_1, ..., T_m$, 而且这些集合的每一个也都是树。树$T_1, ..., T_m$称做这个根的子树。

2. 度

一个节点的子树的个数称做该节点的度。

度数为0的节点称做终（端）节点，或者有时叫做叶。

一个非终节点通常称做一个分支节点。

相对于T，一个节点的级递归地定义为：

根root(T)的级为0，任何其它节点的级相对于包含该节点的root(T)的子树的对应节点的级大于1。

3. 有序树

如果子树$T_1, ..., T_m$在定义b）中的相对顺序重要的话，我们就说该树是有序树；

如果把不把仅仅是节点子树的相对次序不同的两棵树当做不同的树，就说这样的树是有向的，因为考虑的仅仅是节点相对的方向，而不是它们的次序。

除非有明确的说明，本书讨论的所有树都是有序的。

4. 森林

森林是零个或多个不相交的树的集合（通常是一个有序的集合）。表达定义的b）部分的另一种方式是说树的除了根之外的所有节点形成森林。

在抽象的树和森林之间的区别很小。如果删去树的根，我们就有一个森林；反过来，如果在任何森林上增加一个节点，并且把森林中的树当做这个新节点的子树，我们就得到一棵树。因此，关于数据结构的非正式讨论中，树和森林通常几乎是可以互换的。

5. 二叉树

每个节点至多有两个子树的树，称为二叉树；而当只有一棵子树时，我们区分左子树和右子树。更正式地说：

二叉树是节点的有序集合，它或者为空，或者由根和这个根的两个称做左和右子树的不相交的二叉树的元素所组成。

注意：二叉树不是树的特殊情况；它全然是另外一个概念：二叉树可以为空，但树不能。

TAOCP_2.3_树