树的基本概念

树的定义

树是 #card=math&code=n%20%5C%20%28n%5Cge%200%29&id=vcM1G) 个节点的有限集。当 时，称为空树。在任意一颗非空树中应满足：

1. 有且仅有一个特定的称为根的结点。
2. 当 时，其余节点可分为 #card=math&code=m%5C%20%28m%3E0%29&id=u2Ah2) 个互不相交的有限集 ，其中每个集合本身又是一棵树，并称为根的子树。

显然，树的定义是递归的，即在树的定义中又用到了其自身，树是一种递归的数据结构。树作为一种逻辑结构，同时也是一种分层结构，具有以下两个特点：

1. 树的根结点没有前驱，除根结点外的所有结点有且只有一个前驱。
2. 树中所有结点可以有零个或多个后继。

树适合于表示具有层次结构的数据。树中的某个结点（除根结点外）最多只和上一层的一个结点（即其父结点）有直接关系，根结点没有直接上层结点，因此在 个结点的树中有 条边。而树中每个结点与其下一层的零个或多个结点（即其子女结点）有直接关系。

基本术语

• 考虑结点 K 。根 A 到结点 K 的唯一路径上的任意结点，称为结点 K 的祖先。如结点 B 是结点 K 的祖先，而结点 K 是结点 B 的子孙。路径上最接近结点 K 的结点 E 称为 K 的双亲，而 K 为结点 E 的孩子。根 A 是树中唯一没有双亲的结点。有相同双亲的结点称为兄弟，如结点 K 和结点 L 有相同的双亲 E，即 K 和 L 为兄弟。
• 树中一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度。如结点 B 的度为 2，结点 D 的度为 3，树的度为 3。
• 度大于 0 的结点称为分支结点（又称非终端结点）；度为 0 （没有子女结点）的结点称为叶子结点（又称终端结点）。在分支结点中，每个结点的分支数就是该结点的度。
• 结点的层次从树根开始定义，根结点为第 1 层，它的子结点为第 2 层，以此类推。双亲在同一层的结点互为堂兄弟，图中结点 G 与 E，F，H，I，J 互为堂兄弟。
• 结点的深度是从根结点开始自顶向下逐层累加的。
• 结点的高度是从叶结点开始自底向上逐层累加的。
• 树的高度（或深度）是树中结点的最大层数。图中树的高度为 4。
• 有序树和无序树。树中结点的各子树从左到右是有次序的，不能互换，称该树为有序树，否则称为无序树。假设图为有序树，若将子结点位置互换，则变成一棵不同的树。
• 路径和路径长度。树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的，而路径长度是路径上所经过的边的个数。注意：由于树中的分支是有向的，即从双亲指向孩子，所以树中的路径是从上向下的，同一双亲的两个孩子之间不存在路径。
• 森林是 #card=math&code=m%5C%20%20%28m%20%5Cge%200%29&id=Xa2bL) 棵互不相交的树的集合。森林的概念与树的概念十分相近，因为只要把树的根结点删去就成了森林。反之，只要给 棵独立的树加上一个结点，并把这 棵树作为该结点的子树，则森林就变成了树。

度为 的树与 叉树：前者表示树中各节点最少存在一个最大为 度的结点，而 叉树表示每个结点最多只能有 个孩子的树。

树的性质

树具有如下最基本的性质：

1. 树中的结点数等于所有结点的度数加 1。
2. 度为 的树中第 层上至多有 个结点 #card=math&code=%28i%5Cge%201%29&id=rjpNu)。
3. 高度为 的 叉树至多有 个结点。
4. 具有 个结点的 叉树的最小高度为 。[1]

1. 推导过程：

↩︎