【树的定义】
树，是 $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$ 叉树最小高度为 $\left\lceil log_m(n(m-1)+1) \right\rceil$
度为 $m$ 的树与 $m$ 叉树的对比如下表
| 度为 $m$ 的树 | $m$ 叉树 |
|---|---|
| 任意结点的度 $\leq m$（最多 $m$ 个孩子） | 任意结点的度 $\leq m$（最多 $m$ 个孩子） |
| 至少一个结点度 $=m$ （有 $m$ 个孩子） | 允许所有结点的度 $<m$ |
| 一定是非空树，至少有 $m+1$ 个结点 | 可以是空树 |
| 子树不要求有序 | 子树是有序的，次序不能任意颠倒 |
