【树的定义】

树，是 $n (n \geq 0)$ 个结点的有限集合，当 $n = 0$ 时，树称为空树

对于任意一棵非空树，其满足：

有且仅有一个特定的根结点
$n > 1$ 时，其余结点可分为 $m (m > 0)$ 个互不相交的有限集合 $T_{1}, T_{2}, . ., T_{m}$ ，每个集合本身又是一棵树，被称为根结点的子树

树具有以下特点：

是一种递归的数据结构
根结点没有前驱，除根结点外的所有结点有且仅有一个前驱
所有的结点可以有零到多个后继
$n$ 个结点的树有 $n - 1$ 条边

【基本术语】

上端结点为下端结点的父结点（parent node），下端结点为上端结点的子结点（children node），同一个父结点的多个子结点互称兄弟结点（brother node），同一层的结点互称堂兄弟结点（cousin node）

从根结点到某个子结点所经过的所有结点称为这个子结点的祖先（ancestor），以某个结点为根的子树中的任一结点都是该结点的子孙（descendant）

一个结点的孩子个数，称为结点的度（degree），树中各结点的度的最大值称为这棵树的度（tree degree）

度为 $0$ 的结点称为叶结点（leaf node），度不为 $0$ 的结点称为分支结点（branch node），根以外的分支结点称为内部结点（internal node）

连接两个相关联的结点的线段称为树枝（branch）

对于树中任意两个不同的结点，如果从一个结点出发，自上而下沿着树中连着结点的线段能到达另一结点，则称它们之间存在着一条唯一的路径（path），路径上经过的边数称为路径长度（path length），从根结点出发，到树中的其余结点一定存在着一条路径，不同子树上的结点之间不存在路径。

若一棵树中结点的各子树从左到右是有次序的，即若交换结点各子树的相对位置会构成不同的树，则称为有序树（ordered tree），反之，交换结点各子树的相对位置后为同一棵树，则为无序树（unordered tree）

规定一棵树的根结点的层次（level）为 $1$ ，其它结点的层次等于它的父结点层次 $+ 1$

一棵树中所有的结点的层次的最大值称为树的深度（depth）

将树中结点按照从上层到下层，同层中从左到右的次序依次从 1 开始编号，这种编号方式称为层序编号（level code），通过层序编号可以将一棵树变为线性序列

以下图为例：

这棵树的根结点为： $1$ ，叶结点有： $3$ 、 $5$ 、 $6$ 、 $8$ 、 $9$ ，分支结点有： $1$ 、 $2$ 、 $4$ 、 $7$ ，内部结点有： $2$ 、 $4$ 、 $7$ ，整个树的度为： $3$

对于根结点 $1$ 来说，它是 $2$ 、 $3$ 、 $4$ 的父结点，同时 $2$ 、 $3$ 、 $4$ 是结点 $1$ 的子结点，它们又是兄弟结点

对于结点 $8$ 来说， $1$ 、 $4$ 、 $7$ 是它的祖先；对于结点 $4$ 来说， $7$ 、 $8$ 、 $9$ 是它的子孙

根结点 $1$ 的层次为 $1$ ，结点 $2$ 、 $3$ 、 $4$ 的层次为 $2$ ，结点 $5$ 、 $6$ 、 $7$ 的层次为 $3$ ，结点 $8$ 、 $9$ 的层次为 $4$ ，这棵树的深度为 $4$

对于结点 $1$ 与结点 $8$ 之间存在的路径，可用 $1$ 、 $4$ 、 $7$ 、 $8$ 来表示该路径，该路径的长度为 $3$

【树的性质】

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

树中结点数 = 总度数 $+ 1$
度为 $m$ 的树中第 $i$ 层上最多有 $m^{i - 1}$ 个结点
度为 $m$ 的树，若高度为 $h$ ，最少有 $h + m - 1$ 个结点

对于 $m$ 叉树，即每个结点最多只能有 $m$ 个孩子的树来说，其具有以下性质：

高度为 $h$ 的 $m$ 叉树最多有 $\frac{m^{h} - 1}{m - 1}$ 个结点，最少有 $h$ 个结点
$n$ 个结点的 $m$ 叉树最小高度为 $⌈ l o g_{m} (n (m - 1) + 1) ⌉$

度为 $m$ 的树与 $m$ 叉树的对比如下表

度为 $m$ 的树	$m$ 叉树
任意结点的度 $\leq m$ （最多 $m$ 个孩子）	任意结点的度 $\leq m$ （最多 $m$ 个孩子）
至少一个结点度 $= m$ （有 $m$ 个孩子）	允许所有结点的度 $< m$
一定是非空树，至少有 $m + 1$ 个结点	可以是空树
子树不要求有序	子树是有序的，次序不能任意颠倒

Alex_McAvoy

树的基本概念

【树的定义】

【基本术语】

【树的性质】