树（Tree）基本定义

树（Tree）是 n (n >= 0) 个结点构成的有限数据集合。n = 0 时称为空树。在任意一棵非空树中：

有且仅有一个特定的根（Root）结点。
当 n > 1 时，其余结点可分为 m (m > 0) 个互不相交的有限集 T1、T2、......、Tm ，每一个有限集本身也是一颗树，称为根的子树（SubTree）。

图：树（Tree）结构示意图

树（Tree）适用于表示具有「层次结构」的数据类型。树中的每个元素被称为树的结点（Tree Node），有且仅有一个特定的根（Root）结点，树结点具有若干指向子结点的指针域，每个子结点本身也是一颗树。

显然，树的定义是「递归」的，并且树还具有以下特点：

树中根结点无前驱结点，除根结点外的所有结点有且仅有一个前驱结点。
树中所有结点可以有零或多个后继结点。

树（Tree）基本概念

对树的一些基本概念与名词作解释说明。

结点分类

基本概念	解释说明
结点的度（Degree）	结点所具有的子结点个数。
分支结点（Branch）	度大于`0`的结点。
叶子结点（Leaf）	度等于`0`的结点。
树的度（Degree of Tree）	树内各结点的度的最大值。

表：树（Tree）结点分类说明表

结点关系

基本概念	解释说明
祖先结点（Ancestor）	自当前结点上溯至根结点唯一路径上的任意结点。
子孙结点（Child）	自当前结点下溯至叶结点任意路径上的任意结点。
双亲结点（Parent）	最靠近当前结点的祖先结点。
兄弟结点（Sibling）	与当前结点具有相同双亲的结点。

表：树（Tree）结点关系说明表

其他概念

基本概念	解释说明
路径长度（Path）	两个结点之间所经过结点序列边的个数。
结点层次（Level）	当前结点所在树中的层次（层次从`1`开始）。
结点深度（Depth）	从根结点开始自顶向下逐层累加（深度从`0`开始）。
结点高度（Height）	从叶结点开始自底向上逐层累加（高度从`0`开始）。
树的高度/深度（Depth/Height of Tree）	树内各结点的层次的最大值。
森林（Forest）	n (n >= 0) 颗互不相交的树的集合。

表：树（Tree）其他概念说明表

树（Tree）基本性质

树数据结构具有如下几个基本性质：

树的结点数目等于树中所有结点的度数之和再加 1 。
度为 m 的树中，第 i (i >= 1) 层至多有 m^(i-1) 个结点。
高度为 h 的 m 叉树至多拥有 (m^h - 1)/(m - 1) 个结点。
具有 n 个结点的 m 叉树最小高度为 log_m(n(m - 1)) + 1 。