5.1.1　基本概念

1. 树的定义及基本术语

(1) 树的定义。树是由n(n≥0)个结点组成的有限集合。若n=0，称为空树；若n＞0，则

① 有一个特定的称为根(root)的结点。它只有直接后继，但没有直接前驱。

② 除根结点以外的其他结点可以划分为m(m≥0)个互不相交的有限集T₀，T₁，…，T_m，

其中每一个子集本身又是一棵符合本定义的树，称为根的子树，每一棵子树的根有且仅有一个直接前驱，但可以有0个或多个直接后继。

(2) 结点。包含一个数据元素及若干指向其子树的分支。

(3) 结点的度。一个结点包含子树的个数称为该结点的度。

(4) 树的度。树中结点的最大度数。

(5) 叶子(叶结点或终端结点)。树中度为零的结点。

(6) 分支结点(非终端结点)。度不为零的结点。

(7) 路径。如果存在树中的一个结点序列K₁，K₂，…，K_j，使得结点K_i是结点K_i+1的父结点(1≤i≤j)，则称该结点序列是树中从结点K₁到结点K_j的一条路径或道路。我们称这条路径的长度为j-1，它是该路径所经过的边(即连接两个结点的线段)的数目。树中任一结点有一条到其自身的长度为零的路径。

(8) 孩子。结点的子树的根。

(9) 双亲。结点的直接前驱，称为该结点的双亲。

(10) 兄弟。具有同一双亲结点的子结点。

(11) 结点的层数。从树根到任一结点n有唯一的一条路径，我们称这条路径的长度为结点n的层数。根结点的层数为1，其余结点的层数为从根结点到该结点所经过的分支数加1。

(12) 树的深(高)度。树中结点的最大层数称为树的深度(或高度)。

(13) 有序树。树中各结点的子树是按照一定的次序从左向右排列的，且相对次序是不能随意变换的。

(14) 无序树。树中各结点的子树无一定的次序排列，其相对次序是可以随意变换的。

(15) 森林。森林是m(m≥0)棵互不相交的树的集合。

2. 二叉树的定义与性质

(1) 二叉树的定义。二叉树是n(n≥0)个结点的有限集合：

① 或者为空二叉树，即n＝0；

② 或者由一个根结点和两棵互不相交的、被称为根的左子树和右子树所组成。左子树和右子树分别又是一棵二叉树。

(2) 满二叉树。若二叉树中所有的分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树，即深度为K且有2^K-1个结点的二叉树。

(3) 完全二叉树。设一个深度为K的二叉树，每层结点数目如果满足：

① 第i层(1≤i≤K-1)上的结点个数均为2^i-1。

② 第K层从右边起连续缺若干个结点。

这样的二叉树称为完全二叉树。

(4) 二叉树的性质

性质1 在二叉树的第i层上至多有 2^i-1个结点(i≥1)。

性质2 深度为k的二叉树中至多含有2^k-1个结点 (k≥1)。

性质3 对任何一棵二叉树T，如果其终端结点数为n₀，度为2的结点数为n₂，则n₀=n₂+1。

性质4 具有n个结点的完全二叉树的深度为[log₂n] +1。

性质5 如果对一棵有n个结点的完全二叉树(其深度为[log₂n] +1)的结点按层序(从第1层到第 [log₂n] +1层，每层从左到右)从1起开始编号，则对任一编号为i的结点(1≤i≤n)，有

① 如果i=1，则编号为i的结点是二叉树的根，无双亲；如果i＞1，则其双亲结点 Parent(i)的编号是[i/2]。

② 如果 2i＞n，则编号为i的结点无左孩子(编号为i的结点为叶子结点)；否则，其左孩子结点LChild(i) 的编号是 2i。

③ 如果 2i+1＞n，则编号为i的结点无右孩子；否则，其右孩子结点 RChild(i) 的编号是结点 2i+1。

3. 二叉树的存储结构

(1) 顺序存储结构

二叉树顺序存储的定义：按照完全二叉树的结构对二叉树的结点进行编号，用一组地址连续的存储单元依次自上而下、从左至右存储完全二叉树上的结点元素。其中以“0”表示不存在此结点。

二叉树的顺序存储表示如下：

#define MAX_TREE_SIZE 100　　　　//二叉树的最大结点数

typedef TElemType SqBiTree[MAX_TREE_SIZE];　　　//0号单元存储根结点

SqBiTree bt;

其缺点是：空间利用率低，不利于插入和删除。

由此可见，这种顺序存储结构仅适用于完全二叉树。因为，在最坏情况下，一个深度为k且只有k个结点的单支树(树中不存在度为2的结点)却需要长度为2^k-1的一维数组。

(2) 链式存储结构

链式存储结构是指用一个链表来存储一棵二叉树，二叉树中每一个结点用链表中的一个链结点来存储。有二叉链表、三叉链表、双亲链表、线索链表。其中，二叉链表是最常用的存储形式，其结点结构和类型描述如下：

结点结构：

类型描述如下:

4. 二叉树的遍历

二叉树遍历的定义：按某条搜索路径巡访树中每个结点，使得每个结点均被访问一次，而且仅被访问一次的过程。

(1) 先序遍历二叉树

若二叉树为空，则空操作；否则，

① 访问根结点；

② 先序遍历左子树；

③ 先序遍历右子树。

(2) 中序遍历二叉树

若二叉树为空，则空操作；否则，

① 中序遍历左子树；

② 访问根结点；

③ 中序遍历右子树。

(3) 后序遍历二叉树

若二叉树为空，则空操作；否则，

① 后序遍历左子树；

② 后序遍历右子树；

③ 访问根结点。

(4) 层次遍历二叉树

从上层到下层，每层中从左侧到右侧依次访问每个结点。

5. 线索二叉树

利用二叉链表中的空指针域，可以存放指向结点在某种遍历次序下的前驱和后继结点的指针(这种附加的指针称为“线索”)。加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树(Threaded BinaryTree)。根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。

线索链表中的结点结构为：

其中：Ltag和Rtag是增加的两个标志域，用来区分结点的左、右指针域是指向其左、右孩子的指针，还是指向其前驱或后继的线索。

6. 树的存储结构

树的存储结构有三种：双亲表示法、孩子链表表示法、树的二叉链表 (孩子-兄弟)存储表示法。

7. 二叉树与树、森林之间的转换

(1) 树转换为二叉树的步骤

① 加线。同一层次各兄弟结点之间加一连线。

② 抹线。对每个结点，除了保留与其长子(左孩子)的连线外，抹掉该结点原先与其他孩子的连线。

③ 旋转。以树的根结点为轴心，将整树顺时针旋转45°。

转换成的二叉树有以下两个特点：

① 根结点没有右子树。

② 各结点的右孩子是原来树中该结点的兄弟，而该结点的左孩子还是原来树中该结点的孩子。

(2) 森林转换为二叉树的步骤

① 将森林中的每棵树变为二叉树。

② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起。

③ 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转45。，构成二叉树形结构。

(3) 二叉树还原为树的步骤

① 加线。若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子……沿分支找到的所有右孩子，都与p的双亲用线连起来。

② 抹线。抹掉原二叉树中双亲与右孩子之间的连线。

③ 调整。将结点按层次排列，形成树结构。

(4) 二叉树还原为森林的步骤

① 抹线。将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。

② 还原。将孤立的二叉树还原成树。

8. 树和森林的遍历

(1) 树的遍历方法

① 先根(次序)遍历树

若树不空，则先访问根结点，然后依次从左到右先根遍历根的各棵子树。

② 后根(次序)遍历树

若树不空，则先依次从左到右后根遍历根的各棵子树，然后访问根结点。

③ 层次遍历树

与二叉树的层次遍历相似，从上层到下层，每层中从左侧到右侧依次访问每个结点。

(2) 森林的遍历方法

1) 先序遍历森林

若森林非空，则按下述规则进行遍历：

① 访问森林中第一棵树的根结点。

② 先序遍历第一棵树中根结点的子树森林。

③ 先序遍历除去第一棵树之后剩余的树构成的森林。

2) 中序遍历森林

若森林非空，则按下述规则进行遍历：

① 中序遍历第一棵树中根结点的子树森林。

② 访问森林中第一棵树的根结点。

③ 中序遍历除去第一棵树之后剩余的树构成的森林。

当以二叉链表作存储结构时，树的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历算法实现。

9. 哈夫曼树(最优二叉树)

(1) 路径长度。从一个结点到另一个结点的分支数目。

(2) 树的路径长度。从根结点到每一结点的路径长度之和。

(3) 结点的带权路径长度。从树根结点到该结点之间的路径长度与该结点上权的乘积。

(4) 树的带权路径长度。树中所有叶子结点的带权路径长度之和，通常记作：(wk表示叶子结点的权值，l_k表示根到叶子结点的路径长度)。

(5) 哈夫曼树(最优二叉树)

带权路径长度最小的二叉树。