下载掌阅APP，畅读海量书库
立即打开
树是由一个或多个结点组成的有限集合 T ，它满足以下两个条件：
（1）有一个特定的结点，称为根结点；
（2）其余的结点分成 m （ m ≥0）个互不相交的有限集合。其中每个集合又都是一棵树，称 T 1 , T 2 ,…, T m –1 为根结点的子树。
显然，以上定义是递归的，即一棵树由子树构成，子树又由更小的子树构成。由条件（1）可知，一棵树至少有一个结点（根结点）。一个结点的子树数目称为该结点的度（次数），树中各结点的度的最大值称为树的度（树的次数）。度为0的结点称为叶子结点（树叶），除叶子结点外的所有结点称为分支结点，根以外的分支结点称为内部结点。例如，在图1-3所示的树中，根结点的度数为3，结点2的度数为4，结点4的度数为1，结点9的度数为2，其他结点的度数为0，该树的度数4。
图1-3 树的例子
在用图形表示的树中，对两个用线段连接的相关联的结点而言，称位于上端的结点是位于下端的结点的父结点或双亲结点，称位于下端的结点是位于上端的结点的（孩）子结点，称同一父结点的多个子结点为兄弟结点，称处于同一层次上、不同父结点的子结点为堂兄弟结点。例如在图1-3中，结点1是结点2,3,4的父结点。反之，结点2,3,4都是结点1的子结点。结点2,3,4是兄弟结点，而结点5,6,7,8,9是堂兄弟结点。
定义一棵树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1。树中各结点的层次的最大值称为树的层次。
因为树是非线性的结构，为了存储树，必须要把树中结点之间的关系反映在存储结构中。最常用的树的存储结构有标准存储和带逆存储形式。
在树的标准存储结构中，树中的结点内容可分成两部分，分别为结点的数据和指向子结点的指针数组。对于 N 度树，在其标准存储结构中指针数组有 N 个元素。
例如设树的次数为5，树的结点数据仅限于字符，用C语言描述树结点的标准存储结构的数据类型如下：
带逆存储结构在标准存储结构的基础上增加一个指向其父结点的指针，用C语言描述树结点的带逆存储结构的数据类型如下：
按照某种顺序逐个获得树中全部结点的信息，称为树的遍历。常用的树的遍历方法主要有以下3种。
● 前序遍历：首先访问根结点，然后从左到右按前序遍历根结点的各棵子树。
● 后序遍历：首先从左到右按后序遍历根结点的各棵子树，然后访问根结点。
● 层次遍历：首先访问处于0层上的根结点，然后从左到右依次访问处于1层上的结点，然后从左到右依次访问处于2层上的结点等，即自上而下、从左到右逐层访问树中各层上的结点。
按上述遍历的定义，图1-3所示的树的各种遍历结果如下。
● 前序遍历：1，2，5，6，7，8，3，4，9，a，b。
● 后序遍历：5，6，7，8，2，3，a，b，9，4，1。
● 层次遍历：1，2，3，4，5，6，7，8，9，a，b。
二叉树是一个有限的结点集合，该集合或者为空，或者由一个根结点及其两棵互不相交的左、右二叉子树所组成。二叉树的结点中有两棵子二叉树，分别称为左子树和右子树。因为二叉树可以为空，所以二叉树中的结点可能没有子结点，也可能只有一个左子结点（右子结点），也可能同时有左右两个子结点。如图1-4所示是二叉树的4种可能形态（如果把空树计算在内，则共有5种形态）。
图1-4 二叉树的4种不同形态
与树相比，二叉树可以为空，空的二叉树没有结点（树至少有一个结点）。在二叉树中，结点的子树是有序的，分左、右两棵子二叉树。
二叉树常采用类似树的标准存储结构来存储，其结点类型可以用C语言定义如下：
二叉树具有下列重要性质（此处省略了推导过程，有兴趣的读者可自行推导）。
性质1：在二叉树的第 i 层上至多有2 i -1 个结点（ i ≥1）。
性质2：深度为 k 的二叉树至多有2 k –1个结点（ k ≥1）。
性质3：对任何一棵二叉树，如果其叶子结点数为 n 0 ，度为2的结点数为 n 2 ，则 n 0 ＝ n 2 ＋1。
一棵深度为 k 且有2 k -1（k≥1）个结点的二叉树称为满二叉树。如图1-5所示就是一棵满二叉树，对结点进行了顺序编号。
图1-5 满二叉树的例子
如果深度为 k 、有 n 个结点的二叉树中各结点能够与深度为 k 的顺序编号的满二叉树从1到 n 标号的结点相对应，则称这样的二叉树为完全二叉树。如图1-6（a）所示是一棵完全二叉树，而（b）、（c）是两棵非完全二叉树。显然，满二叉树是完全二叉树的特例。
图1-6 完全二叉树和非完全二叉树
根据完全二叉树的定义，显然，在一棵完全二叉树中，所有的叶子结点都出现在第 k 层或 k –1层（最后两层）。
性质4：具有n（n＞0）个结点的完全二叉树的深度为
+1。（注：
符号为向下取整运算符，
为向上取整运算符，
表示不大于m的最大整数，反之，
表示不小于m的最小整数）
性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（从第1层到第
+1层，每层从左到右），则对任一结点i（1≤i≤n），有：
● 如果
i
＝1，则结点
i
无双亲，是二叉树的根；如果
i
＞1，则其双亲是结点
。
● 如果2i＞n，则结点 i 为叶子结点，无左孩子；否则，其左孩子是结点2i。
● 如果2i＋1＞n，则结点 i 无右孩子；否则，其右孩子是结点2i＋1。
树的所有遍历方法也同样适用于二叉树，此外，由于二叉树自身的特点，还有中序遍历方法。
● 前序遍历（先根遍历，先序遍历）：首先访问根结点，然后按前序遍历根结点的左子树，再按前序遍历根结点的右子树。
● 中序遍历（中根遍历）：首先按中序遍历根结点的左子树，然后访问根结点，再按中序遍历根结点的右子树。
● 后序遍历（后根遍历，后序遍历）：首先按后序遍历根结点的左子树，然后按后序遍历根结点的右子树，再访问根结点。
例如如图1-7所示的二叉树，其前序遍历、中序遍历和后序遍历结果分别如下。
图1-7 二叉树遍历的例子
● 前序遍历：1，2，4，5，7，8，3，6。
● 中序遍历：4，2，7，8，5，1，3，6。
● 后序遍历：4，8，7，5，2，6，3，1。
以上3种遍历方法都是递归定义的，可通过递归函数分别加以实现。
性质6：一棵二叉树的前序序列和中序序列可以唯一地确定这棵二叉树。
根据性质6，给定一棵二叉树的前序序列和中序序列，我们可以写出该二叉树的后序序列。例如，某二叉树的前序序列为 ABHFDECKG，中序序列为 HBDFAEKCG，则构造二叉树的过程如图1-8所示。
图1-8 已知前序序列和中序序列，求二叉树的过程
二叉排序树又称为二叉查找树，其定义为二叉排序树或者是一棵空二叉树，或者是具有如下性质（BST性质）的二叉树：
（1）若它的左子树非空，则左子树上所有结点的值均小于根结点；
（2）若它的右子树非空，则右子树上所有结点的值均大于根结点；
（3）左、右子树本身又各是一棵二叉排序树。
例如如图1-9所示就是一棵二叉排序树。
图1-9 二叉排序树的例子
根据二叉排序树的定义可知，如果中序遍历二叉排序树，就能得到一个排好序的结点序列。二叉排序树上有查找、插入和删除等3种操作。下面，我们假设二叉排序树的结点只存储结点的键值，其类型与前面的二叉树的结点类型相同。
静态查找是在二叉排序树上查找键值为key的结点是否存在，这可按以下步骤在二叉排序树ST上找值为key的结点：
● 如果二叉排序树ST为空二叉树，则查找失败，结束查找；
● 如果二叉排序树的根结点的键值等于key，则查找成功，结束查找；
● 如果key小于根结点的键值，则沿着根结点的左子树查找，即将根结点的左子树作为新的二叉排序树ST继续查找；
● 如果key大于根结点的键值，则沿着根结点的右子树查找，即将根结点的右子树作为新的二叉排序树ST继续查找。
在二叉排序树上，为插入和删除操作需要而使用的查找称为动态查找，动态查找应得到两个指针，一个指向键值为key的结点，另一个指向该结点的父结点。为此，查找函数可设4个参数，查找树的根结点指针root，待查找值key，存储键值为key结点的父结点的指针pre，存储键值为key结点的指针p，但函数要考虑以下几种不同情况。
● 二叉排序树为空，查找失败，函数使*p=NULL*，pre=NULL；
● 二叉排序树中没有键值为key的结点，函数一直寻找至查找路径的最后一个结点，*pre指向该结点，*p=NULL，如果插入键值为key的结点，就插在该结点下；
● 查找成功，*p指向键值为key的结点，*p指向它的父结点。
将利用动态查找函数确定新结点的插入位置，然后分以下几种情况进行相应的处理。
● 如果相同键值的结点已在二叉排序树中，则不再插入；
● 如果二叉排序树为空树，则以新结点为二叉排序树；
● 将要插入结点的键值与插入后的父结点的键值比较，就能确定新结点是父结点的左子结点，还是右子结点，并进行相应插入。
删除二叉排序树上键值为key的结点的操作如下。
● 调用查找函数确定被删结点的位置；
● 如被删结点不在二叉排序树上，则函数返回。
否则，按以下情况分别处理。
● 如果被删除的结点是根结点，又可分两种情况：
▶ 被删除结点无左子树，则以被删除结点的右子树作为删除后的二叉排序树；
▶ 被删除结点有左子树，则以被删除结点的左子结点作为根结点，并把被删除结点的右子树作为被删除结点的左子树按中序遍历的最后一个结点的右子树。
● 如果被删除结点不是根结点，且被删除结点无左子结点：
▶ 被删除结点是它的父结点的左子结点，则把被删除结点的右子树作为被删除结点的父结点的左子树；
▶ 被删除结点是它的父结点的右子结点，则把被删除结点的右子树作为被删除结点的父结点的右子树；
● 如果被删除结点不是根结点，且被删除结点有左子结点，则被删除结点的右子树作为被删除结点的左子树按中序遍历的最后一个结点的右子树，同时进行以下操作：
▶ 被删除结点是它的父结点的左子结点，则把被删除结点的左子树作为被删结点的父结点的左子树；
▶ 被删除结点是它的父结点的右子结点，则把被删除结点的左子树作为被删除结点的父结点的右子树。
为了保证二叉排序树的高度为log 2 n，从而保证二叉排序树上实现的插入、删除和查找等基本操作的平均时间为O(log 2 n)，在往树中插入或删除结点时，要调整树的形态来保持树的“平衡”。使之既保持BST性质不变，又保证树的高度在任何情况下均为log 2 n，从而确保树上的基本操作在最坏情况下的时间均为O(log 2 n)。
平衡二叉树（Balanced Binary Tree或Height-Balanced Tree）又称为AVL树，是指树中任一结点的左右子树的高度大致相同。如果任一结点的左右子树的高度均相同（如满二叉树），则二叉树是完全平衡的。通常，只要二叉树的高度为O(1og 2 n)，就可看做是平衡的。
平衡的二叉排序树指满足BST性质的平衡二叉树。AVL树中任一结点的左、右子树的高度之差的绝对值不超过1。若将二叉树上结点的平衡因子定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子只可能是–1、0和1。
在最坏情况下，n个结点的AVL树的高度约为1.44log 2 n。而完全平衡的二叉树度高约为log 2 n，AVL树是接近最优的。
二叉树在一般情况下无法直接找到某结点在某种遍历序列中的前驱和后继结点。若增加指针域来存放结点的前驱和后继结点信息，将大大降低存储空间的利用率。考查 n 个结点的二叉树，其中有 n +1个空指针域，它们可以被用来存放“线索”，增加了线索的二叉树称为线索树（穿线树）。
设有一棵采用标准形式存储的二叉树BT，对于BT中的每个结点k，如它没有左（或右）子结点，而k1是k的按中序遍历的前面（或后面）结点，则置结点k的左（或右）指针为k1结点的指针。为了与k结点的真正子结点指针区别，另需在结点上增加两个标志域ltag和rtag。如此改造后的线索树的结点类型定义如下：
当ltag=0时，表示lchild指针指向其左孩子结点；当ltag=1时，表示lchild指针指向其前驱结点。当rtag=0时，表示rchild指针指向其右孩子结点；当rtag=1时，表示rchild指针指向其后继结点。
树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。在一些应用中，赋予树中结点的一个有某种意义的实数，这些数字称为结点的权。结点到树根之间的路径长度与该结点上权的乘积，称为结点的带权路径长度。树中所有叶结点的带权路径长度之和，称为树的带权路径长度（树的代价），通常记为：
其中 n 表示叶子结点的数目， w i 和 l i 分别表示叶结点k i 的权值和根到结点k i 之间的路径长度。
在权值为 w l , w 2 ,…, w n 的 n 个叶子所构成的所有二叉树中，带权路径长度最小（即代价最小）的二叉树称为最优二叉树或哈夫曼树。
假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。 n 个权值分别设为 w 1 ,w 2 ,…, w n ，则哈夫曼树的构造规则为：
①将 w 1 , w 2 ,…, w n 看成是有 n 棵树的森林（每棵树仅有一个结点）；
②在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
③从森林中删除选取两棵树，并将新树加入森林；
④重复第②和③步，直到森林中只剩一棵树为止，该树即为所求的哈夫曼树。
例如如果叶子结点的权值分别为1,2,3,4,5,6，则构造哈夫曼树的过程如图1-10所示。
图1-10 哈夫曼树的构造过程
在构造哈夫曼树的过程中，每次都是选取两棵最小权值的二叉树进行合并，因此使用的是贪心算法。
给定结点序列＜ c i ， p i ＞（ c i 为编码字符， p i为 c i 的频度），哈夫曼编码的过程如下：
● 用字符 c i 作为叶子， p i 作为 c i 的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为0和1；
● 将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码。
给定字符集的哈夫曼树生成后，求哈夫曼编码的具体实现过程是依次以叶子结点C[ i ]（0≤ i ≤ n –1）为出发点，向上回溯至根为止。上溯时走左分支则生成代码0，走右分支则生成代码1。需要注意以下几个问题。
● 由于生成的编码与要求的编码反序，将生成的代码先从后往前依次存放在一个临时串中，并设一个指针start指示编码在该串中的起始位置（start初始时指示串的结束位置）。
● 当某字符编码完成时，从临时串的start处将编码复制到该字符相应的位串bits中即可。
● 因为字符集大小为n，故变长编码的长度不会超过n，加上一个结束符“\0”，bits的大小应为n+1。
给定一个序列的集合，若不存在一个序列是另一个序列的前缀，则该序列集合称为前缀码。相反，给定一个序列的集合，若不存在一个序列是另一个序列的后缀，则该序列集合称为后缀码。平均码长或文件总长最小的前缀编码称为最优的前缀码，最优的前缀码对文件的压缩效果亦最佳。
其中， p i 为第 i 个字符的概率， l i 为码长。
利用哈夫曼树很容易求出给定字符集及其概率（或频度）分布的最优前缀码。哈夫曼编码是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据文件压缩掉20%～90%，其压缩效率取决于被压缩文件的特征。