作者：吴华骅 钟希鸣 田冰航
3.1 树的定义
3.1.1 树的基本定义
树(tree)是n(n≥0)个结点的有限集。n=0时称为空树。在任意一棵非空树中：(1)有且仅有一个特定的称为根(root)的节点；(2)当n>1时，其余结点可分为m个互不相交的有限集T1、T2、T3……Tm，其中每一个集合本身又是一棵树，并且称为根的子树(subtree)，如图3-1-1所示
图3-1-1
3.1.2 结点的相关概念
树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(degree)。度为0的结点称为叶结点(leaf)或终端结点；度不为0的结点称为非终端结点或分支结点。除根结点外，分支结点也称为内部结点。树的度是树内各结点度的最大值。如图3-1-2所示，因为这棵树结点度的最大值是结点D的度，为3，所以树的度也为3。
图3-1-2
结点的子树的根称为该结点的孩子(child)，相应地，该结点称为孩子的双亲(parent)（笔者按:私以为以英文原意来看，所谓双亲的译法易造成歧义，应理解为某一位直系亲属）。同一个双亲的孩子之间互称兄弟(sibling)。结点的祖先是从根到该结点所经分支上的所有结点。所以对于H来说，D、B、A都是它的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。B的子孙有D、G、H、I，如图3-1-3所示
图3-1-3
3.1.3 树的其他相关概念
结点的层次(level)从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第m层，则其子树的根在第m+1层。其双亲在同一层的结点互为堂兄弟。如图3-1-4中的D、E、F是堂兄弟，而G、H、I与J也是堂兄弟。树中结点的最大层次称为树的深度(depth)或高度，当前树的深度为4。
图3-1-4
如果将树中结点的各子树看成从左至右是有次序、不能互换的，则称该树为有序树，否则为无序树。
森林(forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
3.2 树的储存结构
3.2.1 双亲表示法
一棵树中除根结点外每个结点有且仅有一个双亲。假设以一组连续空间存储树的结点，同时在每个结点中，附设一个指示器指示其双亲结点在数组中的位置。如图3-2-1为双亲表示法的结构定义代码。
图3-2-1
由此我们可以实现双亲表示法了。由于根结点没有双亲，约定根结点位置域设为-1，则所有结点都有双亲的位置。如图3-2-2中的树结构可由图3-2-3中的双亲表所表示。
图3-2-2
图3-2-3
若增加一个结点最左边孩子的域，不妨称之为长子域，则可以更方便地得到结点的孩子。若无孩子，则长子域设为-1，如图3-2-4所示。
图3-2-4
若还需关注各兄弟之间的关系，则可以增加一个右兄弟域体现此关系。同样的，若无右兄弟，则右兄弟域设为-1，如图3-2-5所示。
图3-2-5
实际运用中可根据实际需求灵活设置指针域。
3.2.2 孩子表示法
由于每个结点可能有多棵子树，可以考虑用多重链表。即每个结点有多个指针域，其中每个指针指向一棵子树的根结点，该方法称为多重链表表示法。然而树各结点的度各不相同，可以设计三种方案解决。
方案一
令指针域的个数就等于树的度。由于树的度是各个结点度的最大值，则可表示所有结点。如图3-2-6所示。
图3-2-6
这种方法思路较为简单直接，但对于各结点的度相差较大时，显然十分浪费空间。
方案二
令各结点指针域的个数等于该结点的度，并专门设一数据域存储该结点的度数。如图3-2-7所示。
图3-2-7
该方法克服了浪费空间的缺点，但由于各结点链表是不相同的结构，运算时会带来时间上的损耗。
方案三
即所谓孩子表示法。将每个结点的孩子结点排列起来，以单链表为存储结构，则n个结点有n个孩子链表，若为叶子结点则此单链表为空。然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中，如图3-2-8所示。
图3-2-8
代码定义如图3-2-9所示
图3-2-9
当然也可将双亲表示法与孩子表示法综合，则可以很方便地得知一个结点的双亲和所有孩子，如图3-2-10所示。
图3-2-10
3.3 二叉树的定义
3.3.1 二叉树的基本定义
二叉树(binary tree)是n(n≥0)个结点的有限集合，该集合或为空集(称为空二叉树)，或由一个根结点和两棵互不相交的，分别称为根结点的左子树和右子树的二叉树组成。如图3-3-1就是一棵二叉树。而图3-2-2中的树，由于D结点有三个子树，所以它不是二叉树。
图3-3-1
3.3.2 二叉树特点
(1)每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。
(2)左子树与右子树有顺序之分，其次序不可任意颠倒。
(3)即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。
3.3.3 二叉树基本形态
(1)空二叉树
(2)只有一个根结点
(3)根结点只有左子树
(4)根结点只有右子树
(5)根结点既有左子树又有右子树。
由于左右子树的区分，图3-3-2中树2、树3、树4和树5分别代表不同的二叉树。
图3-3-2
3.3.4 特殊二叉树
3.3.4.1 斜树
所有结点都只有左子树的二叉树称为左斜树，反之称为右斜树，二者统称为斜树。图3-3-2中树2与树5即为斜树。斜树的每一层都只有一个结点，结点的个数与二叉树深度相同。
3.3.4.2 满二叉树
一棵二叉树中，若所有分支结点都存在左子树与右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。如图3-3-3所示。
图3-3-3
满二叉树的特点有：
(1)叶子只能出现在最下一层。
(2)非叶子结点的度一定是2。
(3)在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。
3.3.4.3 完全二叉树
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这样的二叉树称为完全二叉树。最下一层结点从右向左连续缺少是定义的关键所在。如图3-3-4所示即为一棵完全二叉树。而图3-3-5中三棵二叉树由于1~h-1层出现缺失或最下一层左侧出现空档，都不为完全二叉树。
图3-3-4
图3-3-5
完全二叉树的特点：
(1)叶子结点只出现在最下两层。
(2)最下层叶子一定集中于左侧连续位置。
(3)倒数二层，若有叶子结点，一定都在右部连续位置。
(4)若结点数为1，则该结点只有左孩子，即不存在只有右孩子的情况。
(5)同样结点数的二叉树，完全二叉树的深度最小。
3.4 二叉树的性质
(1)二叉树的第i层上最多有2^i-1个结点(i>=1)。
(2)在一棵深度为k的二叉树中，最多有2^k-1个结点(即满二叉树)，最少有k个结点(即斜树)。
(3)在一棵二叉树中，如果叶子结点的个数为n0，度为2的结点个数为n2，则n0=n2+1。
(4)具有n个结点的完全二叉树的深度为⌊log2(n)⌋+1。(⌊x⌋代表不大于x的最大整数)。
(5)对一棵具有n个结点的完全二叉树中的结点从1开始按层序编号，则对于任意的编号为i（1<=i<=n）的结点，有：
1.如果i>1，则结点i的双亲编号为⌊i/2⌋；否则结点i是根结点，无双亲。
2.如果2i<=n，则结点i的左孩子的编号为2i；否则结点i无左孩子。
3.如果2i+1<=n，则结点i的右孩子的编号为2i+1；否则结点i无右孩子。
3.5 二叉树的存储结构
3.5.1 二叉树顺序存储结构
二叉树顺序存储结构即用一维数组存储二叉树中的结点，结点存储位置与结点间逻辑关系由数组下标体现。如图3-4-1的二叉树可由其下的数组表示
图3-5-1
由图可得，数组元素默认按完全二叉树位置排列，若该位置为空，则用“^”符号表示。可见，当二叉树层次较高而结点较少时(极端情况即为斜树)，存储空间浪费较大。所以该存储结构一般仅用于完全二叉树。
3.5.2 二叉链表
二叉树每个结点最多有两个孩子，所以在链式存储结构中，可为它设计一个数据域和两个指针域，这样的链表称为二叉链表。结构定义代码如图3-5-2，结构示意图如图3-5-3。
图3-5-2
图3-5-3
若有需要，可增添一个指向双亲的指针域，即三叉链表，与树的孩子双亲表示法思路类似，此处不作赘述。
3.6 二叉树的遍历
3.6.1 定义
二叉树的遍历(traversing binary tree)是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。
3.6.2 二叉树遍历方法
基本原理：递归与栈
3.6.2.1 前序遍历
若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再后序遍历右子树。如图3-6-1所示，遍历的顺序为：ABDGHCEIF，代码如图3-6-2所示。
图3-6-1
图3-6-2
算法流程(中、后序算法与之类似，后不再赘述)
以图3-6-3所示二叉树T为例，该数用二叉链表形式存储。
图3-6-3
(1)调用&&&(T)，T根结点不为NULL，所以执行printf，打印字母A，如图3-6-4所示
图3-6-4
(2)调用&&&(T->lchild)；访问了A结点的左孩子，不为NULL，执行printf显示字母B，如图3-6-5所示。
图3-6-5
(3)此时再次递归调用&&&(T->lchild)；访问了B结点的左孩子，执行printf显示字母D，如图3-6-6所示。
]
图3-6-6
(4)再次递归调用&&&(T->lchild)；访问了D结点的左孩子，执行printf显示字母H，如图3-6-7所示。
图3-6-7
(5)再次递归调用&&&(T->lchild)；访问了H结点的左孩子，此时因为H结点无左孩子，所以T==NULL，返回此函数，此时递归调用&&&(T->rchild)；访问了H结点的右孩子，printf显示字母K，如图3-6-8所示。
图3-6-8
(6)再次递归调用&&&(T->lchild)；访问K结点的左孩子，K结点无左孩子，T==NULL，返回，调用&&&(T->rchild)，亦为NULL，返回。于是此函数执行完毕，返回到上一级的递归函数(即打印H结点时的函数)，也执行完毕，返回到打印结点D时的函数，调用&&&(T->rchild)；访问D结点的右孩子，不存在，返回到B结点，调用&&&(T->rchild)；找到了结点E，打印字母E，如图3-6-9所示。
图3-6-9
(7)由于结点E没有左右孩子返回打印B结点时的递归函数，递归执行完毕，返回到最初的&&&，调用&&&(T->rchild)；访问结点A的右孩子，打印字母C，如图3-6-10所示。
图3-6-10
(8)之后类似前面的递归调用，依次继续打印F、I、G、J，最后依次返回，直至最初的&&&执行完毕，步骤略。
3.6.2.2 中序遍历
若树为空，则空操作返回，否则从根结点开始(注意并不是先访问根结点)，中序遍历根结点的左子树，然后是访问根结点，最后中序遍历右子树，如图3-6-11所示。遍历顺序为GDHBAEICF，代码如图3-6-12所示。
图3-6-11
中序遍历算法则将打印结点置于调用左子树函数与调用右子树函数之间即可。
图3-6-12
3.6.2.3 后序遍历
若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。如图3-6-13所示。遍历顺序为GHDBIEFCA，代码如图3-6-14所示。
图3-6-13
后序遍历算法则将打印结点置于调用左子树函数与调用右子树函数之后即可。
图3-6-14
3.6.2.4 层序遍历
若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。如图3-6-15所示。遍历顺序为ABCDEFGHI。
图3-6-15
层序遍历通常用队列实现，代码如3-6-16所示。
图3-6-16
3.6.3 *栈的方法实现二叉树遍历
用栈实现二叉树的遍历，实质上即为将递归左右子树的过程利用栈的后进后出性而以栈的出栈入栈实现。代码实现如图所示(由于C++中对栈的操作较为简易，以下代码由C++实现，建议同学在了解C++对栈操作的各函数之后再行浏览本节)。
图3-6-17 前序遍历
图3-6-18 中序遍历
图3-6-19 后序遍历
3.6.4 * 二叉树遍历的python实现
如图给出二叉树遍历的python实现作为参考，有一定python基础的同学可以以此加深对二叉树遍历原理的领会。
图3-6-20 树的结点定义
图3-6-21 树的定义
图3-6-22 树的前序遍历
图3-6-23 树的中、后序遍历
图3-6-24 树的层序遍历
图3-6-25 主函数
3.7 二叉树的建立
二叉树的建立通常通过输入树的前序、中序或后序式，再进行遍历操作实现(即将前述遍历结点中的打印结点操作改为输入结点操作即可)。
如图3-7-1所示的树，为了能让每个结点确认是否有左右孩子，我们对他进行了扩展，转化为如图3-7-2的模式。即将二叉树中每个结点的空指针引出一个虚节点，其值为一特定值，比如“#”。可称处理后的二叉树为原二叉树的扩展二叉树。扩展二叉树即可实现一个遍历序列确定唯一一棵二叉树。则该树前序遍历序列即为AB#D##C##,代码如图3-7-3所示。
图3-7-1
图3-7-2
相应的，自然也可以使用中序与后序式建立二叉树，只需改动生成根结点的位置即可。
图3-7-3
3.8 线索二叉树
3.8.1 线索二叉树原理
如图3-8-1，在实际中使用二叉树时，存在大量空指针域。而由二叉树性质可知，对于一个结点数为n的二叉树存在n+1个空指针。这无疑造成了空间上的极大浪费。同时，在未对二叉树进行遍历时，我们无法得知该二叉树在前序、中序或后序式中前驱和后继分别是哪个结点，每次需得知是都需遍历一次二叉树，又造成时间上的极大浪费。
从以上角度来看，则可以利用这些空指针域进行某种顺序式前驱和后继的标识。这种指向前驱和后继的指针称为线索，加上线索的二叉链表称为线索链表，相应的二叉树则称为线索二叉树(thread binary tree)。
如图3-8-1中的二叉树，存在11个空指针。将这棵二叉树进行中序遍历后，将所有空指针域中的rchild，改为指向他的后继结点。于是可知图中H的后继为D，I的后继为B，J的后继为E，E的后继为A，F的后继为C，G的后继因为不存在而指向NULL。此时共有6个空指针被利用(如图3-8-2)。
图3-8-1
图3-8-2
再将二叉树中所有空指针域中的lchild，改为指向当前结点的前驱。则H的前驱为NULL，I的前驱为D，J的前驱为B，F的前驱为A，G的前驱为C(如图3-8-3)。至此所有空指针域都被利用。
图3-8-3
通过图3-8-4(空心箭头实线为前驱，虚线黑箭头为后继)，可直观地看出，所谓线索二叉树，实质上即将二叉树转化为双向链表，这样对插入、删除结点、查找某个结点带来方便。对二叉树以某种次序遍历使其变为线索二叉树的过程称为线索化。
图3-8-4
然而此时却无法区分某一结点的lchild指向前驱还是左孩子，rchild是指向后继还是右孩子。则可与每个结点处增添两个标志域ltag与rtag。ltag与rtag为布尔型变量，所占用内存量远小于节省的指针域所占用内存量。可规定ltag/rtag=0时指向前驱或后继，为1时指向左右孩子。即可达到区分效果。
3.8.2 线索二叉树结构实现
线索二叉树存储结构定义代码如图3-8-5所示
图3-8-5
线索化实质即将二叉链表中的空指针改为指向前驱或后继的线索。由于前驱和后继的信息只有在遍历该二叉树时才能得到，则线索化的过程即为在遍历的过程中修改空指针的过程。
中序遍历线索化代码如图3-8-6所示
图3-8-6
可见该过程与中序遍历的递归过程几乎一致，仅将打印链表的过程改为线索化的过程。线索化过程原理如下。
if(!p->lchild)表示若某结点左指针域为空，由于其前驱结点刚被访问过，且赋给了pre，则可将pre赋值给p->lchild，并将p->ltag置为0以完成前驱结点的线索化。后继由于此时并为访问，则可对其前驱结点pre的rchild进行判断，if(!pre->rchild)表示若其右指针域为空则可将其后继结点p赋值给pre->rchild，并将p->rtag置为0，则又完成后继结点的线索化。判断结束后将当前结点赋值给pre，以保持pre指向p的前驱。
如图3-8-7所示，在二叉树线索链表上添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向中序遍历时访问的最后一个结点。且令二叉树中序遍历的第一个结点的lchild域指针与最后一个结点的rchild域指针均指向头结点。则实际上得到了一个双向链表结构。遍历代码如图3-8-8所示。
图3-8-7
图3-8-8
算法原理如下：
(1)第5行，令p=head->lchild，即令p指向根结点开始遍历。
(2)第6~17行，while(p!=head)的大循环即确定循环结束条件为p再次指向头结点。
(3)第8~10行，while(p->ltag==link)，即递归算法中不断调用左子树，直至某结点的ltag不为link(即该结点左子树为空)，打印该结点(即该结点结点调用左子树方程结束，打印结点)。
(4)第11~15行while(p->rtag==thread&&p->rchild!=head),则沿指向后继的指针移动并打印结点。直至p所指向结点有右子树或遍历结束。
(5)第16行，p=p->rchild，进入p的右子树再次进行循环，直至遍历结束。
3.9 树、森林与二叉树的转换
我们对二叉树的各项性质与结构已研究得较为透彻，则对于一般的树和森林，可以转化为二叉树进行研究。
3.9.1 树转换为二叉树
步骤如下(如图3-9-1)：
(1)加线。在所有兄弟结点之间加一条连线。
(2)去线。对树中每个结点，只保留其与第一个孩子结点的连线，删除其与其他孩子结点间的连线。
(3)层次调整。以树的根结点为轴心，将整棵树顺时针旋转一定角度，使之结构层次分明。令第一个孩子为二叉树结点的左孩子，兄弟转换过来的结点是结点的右孩子。
图3-9-1
3.9.2 森林转换为二叉树
步骤如下(如图3-9-2)： (1)把每个树转换成二叉树。
(2)第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树的根结点的右孩子，并用线连接起来。
图3-9-2
3.9.3 二叉树转换为树
二叉树转换为树实则即为树转换为二叉树的逆过程，步骤如下(如图3-9-3)：
(1)加线。若某结点的左孩子结点存在，则将此左孩子的右孩子结点，及右孩子结点的右孩子结点……直至某结点的右孩子结点无右孩子结点，将这些结点都作为此结点的孩子，并用线连接起来。
(2)去线。删除原二叉树中所有结点与其右孩子的连线。
(3)层次调整。使之结构层次分明。
图3-9-3
3.9.4 二叉树转换为森林
首先判断一棵二叉树是否能够转换为森林。若有右孩子，则可转换为森林(原因由二叉树转换为森林方法可轻易得知)。
步骤如下(如图3-9-4)：
(1)从根结点开始，若右结点存在，则将与右结点的连线删除，再查看分离后的二叉树，若右孩子存在，则连线删除。直至所有右孩子连线都删除为止，得到分离的二叉树。
(2)再将每棵分离后的二叉树转换为树即可。
图3-9-4
3.10 赫夫曼树及其应用
3.10.1 赫夫曼树的定义与构造
定义从树中一个结点到另一个结点之间的分支构成两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度即从根结点到每一结点的路径长度之和。若一棵树中结点带有权值，则结点的带权路径长度为从该结点到根结点之间的路径长度与结点上权的乘积，树的带权路径长度即为树中所有叶子结点的带权路径长度之和。
假设有n的权值{w1,w1,w3……wn}，以之构造一棵有n个叶子结点的二叉树，则其中带权路径长度WPL最小的二叉树称为赫夫曼树。
构造赫夫曼树步骤如下：
(1)假设有A、B、C、D、E五个叶子结点，权值分别为5、15、40、30、10.则先将其按从小到大的顺序排列成一个有序序列，即：A5,E10,B15,D30,C40。
(2)取权值最小与第二小的的两个结点作为一个新节点N1的两个子节点，取相对较小者为左孩子，如图3-10-1所示。新结点权值为两叶子结点之和。
图3-10-1
(3)将N1替换A与E，插入有序序列中，保持从小到大排列。即：N1 15,B15,D30,C40.
(4)重复步骤2，将N1与B作为一个新结点N2的两个子结点。如图3-10-2所示。N2的权值为30。
图3-10-2
(5)不断重复步骤3,4，直至所有叶子结点都在一个二叉树中。最终构成的二叉树即为给定结点的赫夫曼树。如图3-10-3所示。
图3-10-3
此时树的WPL最短，为40×1+30×2+15×3+10×4+5×4=205。
算法描述如下：
(1)根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均为空。
(2)在F中选取两棵根结点权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树根结点的权值为其左右子树上根结点的权值之和。
(3)在F中删除这两棵树，同时将新得到的二叉树加入F中。
(4)重复步骤2,3，直至F中只含一棵树为止。该树即为给定结点的赫夫曼树。
3.10.2 赫夫曼树的应用
3.10.2.1 设置判断条件
对于某些需要进行多步判断条件的问题，可以应用赫夫曼树找出最优的判断条件。
如下面这个情景：学校把学生的成绩分为五个等级:059为E,6069为D,7079为C,8089为B,90~100为A，所占比例分别为5%,15%,40%,30%,10%，现要按标准等级制录入学生成绩。
通常直接想到的判断方法显然是逐个判断条件，如图3-10-4所示。
图3-10-4
但由于各等级段学生比例并不相同，即各结点权值不同，这样效率并不高。经过计算得WPL=5×1+15×2+40×3+30×4+10×4=315。
而对该结点创建赫夫曼树，即3-10-3所创建的赫夫曼树，WPL=205，效率提升了1/3，在所需判断次数较多的情况下，效率提升的效果是极为显著的。
3.10.2.2 赫夫曼编码
赫夫曼研究这种最优树的目的是为了解决当年远距离通信（主要是电报）的数据传送的最优化问题。
我们以网络传输一段文字内容为“BADCADFEED”为例。如果用二进制的数字（0和1）来表示，如图3-10-5所示。
图3-10-5
真正传输的数据就是编码后的“001000011010000011101100100001”。若传输一篇很长的文章，此二进制串显然较大，而不同字母的出现频率并不相同。假设这六个字母的频率如图3-10-6所示。
图3-10-6
则可尝试构造字母的赫夫曼树，如图3-10-7所示(右侧为将权值的左右分支分别改为0和1之后的赫夫曼树)。
图3-10-7
此时，我们对这六个字母用其从树根到叶子所经过路径的0或1来编码，得到下表(如图3-10-8所示)
图3-10-8
同时，由于有长短不一的编码，必须运用前缀编码原则，即任一字符的编码都不是另一字符的前缀。显然，图3-10-8中的编码不存在易与1001、1000混淆的10和100编码。
再次编码为“1001010010101001000111100”。
显然新字符串较原字符串变小了，节约了大约17%的存储或传输成本。随着字符串的增加和多字符权重的不同，这种压缩将更显优势。
而接收方解压缩时，则使用与发送方相同的赫夫曼编码原则解码即可。