第7章 树和二叉树 7.1 树 7.2 二叉树 7.3 以结点类为基础的二叉树设计 7.4 二叉树类 7.5 二叉树的分步遍历 第7章 树和二叉树 7.1 树 7.2 二叉树 7.3 以结点类为基础的二叉树设计 7.4 二叉树类 7.5 二叉树的分步遍历 7.6 线索二叉树 7.7 霍夫曼树 7.8 树的遍历

本章主要知识点： 树的定义、表示方法和存储结构 二叉树的定义、性质和存储结构，满二叉树和完全二叉树的概念 二叉树的前序、中序、后序和层序遍历算法 二叉树中序和层序游标类的设计方法 线索二叉树的基本概念 哈夫曼树和哈夫曼编码，哈夫曼编码的软件设计方法 树与二叉树的转换，树的遍历

7.1 树 7.1.1 树的定义 树是由n（n≥0）个结点构成的满足以下条件的结点集合： （2）当n>1时，除根结点外的其他结点被分成m（m>0）个互不相交的集合T1, T2,…, Tm，其中每一个集合Ti（1≤i≤m）本身又是一棵结构和树结构类同的子树。

树的示例： 只有根结点的树 一般的树

结点：结点由数据元素和构造数据元素之间关系的指针 组成。 结点的度：结点所拥有的子树的个数称为该结点的度。 叶结点：度为0的结点称为叶结点，叶结点也称作终端结点。 分支结点：度不为0的结点称为分支结点，分支结点也称 作非终端结点。 孩子结点：树中一个结点的子树的根结点称作这个结点 的孩子结点。 孩子结点也称为直接后继结点。

双亲结点：若树中某结点有孩子结点，则这个结点就称作它的孩子结点的双亲结点。 双亲结点也称为直接前驱结点。 兄弟结点：具有相同的双亲结点的结点称为兄弟结点。 树的度：树中所有结点的度的最大值称为该树的度。 结点的层次：从根结点到树中某结点所经路径上的分支数。根结点的层次规定为0，这样其他结点的层次就是他的双亲结点的层次加1. 树的深度：树中所有结点的层次的最大值称为该树的深度。

无序树：树中任意一个结点的各孩子结点的排列没有严格次序的树称为无序树。 从前面树的定义可知，树是无序树。 有序树：树中任意一个结点的各孩子结点的排列有严格次序的树称为有序树。 后面讨论的二叉树是一种有序树。 森林：m（m≥0）棵树的集合称为森林。 一棵树由根结点和m个子树组成，若把树中的根结点删除，则树就变成了包含m棵树的森林。当然，一棵树也可以称为森林。

7.1.2 树的表示方法 1 直观表示法

2 形式化表示法 树的形式化表示法主要用于树的理论描述。树的形式化表示法定义树T为T=（D，R）其中D为树T中结点的集合，R为树T中结点之间关系的集合。当树T为空树时D=￠；当树T不为空树时有D={Root}∪DF，其中Root为树T的根结点，DF为树T的根Root的子树集合，DF可由下式表示： DF = D1∪D2∪…∪Dm （1≤i,j≤m, Di∩Dj=￠）

树的凹入表示法（或称缩进表示法）是一种结点逐层缩进的表示方法。树的凹入表示法还可以分为横向凹入表示和竖向凹入表示。 3 凹入表示法 直观表示法B图的凹入表示： 树的凹入表示法（或称缩进表示法）是一种结点逐层缩进的表示方法。树的凹入表示法还可以分为横向凹入表示和竖向凹入表示。 树的横向凹入表示

7.13 树的抽象数据类型 数据集合 ：树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。 操作集合： （1）双亲结点parent() （2）左孩子结点leftChild() （3）右兄弟结点rightSibling() （4）遍历树traverse(vs)

7.1.4 树的存储结构 1 双亲表示法 双亲表示法就是用指针表示出每个结点的双亲结点。 对于使用仿真指针的双亲表示法来说，每个结点应有两个域，一个是数据元素域，另一个是指示其双亲结点在数组中下标序号的仿真指针域。

双亲表示法对于寻找一个结点的双亲结点操作实现很方便，但对于寻找一个结点的孩子结点操作实现却很不方便。 树及其使用仿真指针的双亲表示法 双亲表示法对于寻找一个结点的双亲结点操作实现很方便，但对于寻找一个结点的孩子结点操作实现却很不方便。

2 孩子表示法 孩子表示法就是用指针表示出每个结点的孩子结点。 常规指针的孩子表示法

由于树中每个结点的子树个数（即结点的度）不同，如果按照各个结点的度设计变长的每个结点的孩子结点指针域个数，则算法实现非常麻烦 孩子表示法可按树的度（即树中所有结点度的最大值）设计结点的孩子结点指针域的个数。 孩子表示法和双亲表示法的特点刚好相反。孩子表示法对于寻找一个结点的孩子结点操作实现很方便，但对于寻找一个结点的双亲结点操作很不方便。

3 双亲孩子表示法 双亲孩子表示法就是用指针既表示出每个结点的双亲结点，也表示出每个结点的孩子结点。 双亲孩子表示法存储结构具有双亲表示法和孩子表示法两种存储结构的优点。

4 孩子兄弟表示法 孩子兄弟表示法就是用指针既表示出每个结点的孩子结点，也表示出每个结点的兄弟结点。

在使用孩子兄弟表示法的存储结构中，每个结点最多只有两个指针域，并且这两个指针含义是不同的，所以孩子兄弟表示法对应的实际是一种二叉树。 孩子兄弟表示法的最大的优点是可以按照二叉树的处理方法来处理树。 孩子兄弟表示法是使用最多的树的存储结果。 实际使用中，经常将树问题转换为二叉树问题来处理。

7.2 二叉树 7.2.1 二叉树的定义 二叉树是n（n≥0）个结点构成的、每个结点最多只有两个子树的有序树。二叉树的结点形态：空结点，无左右子树结点，只有左子树结点，只有右子树结点和左右子树均存在结点。 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上。 完全二叉树：如果一棵具有n个结点的二叉树的逻辑结构与满二叉树的前n个结点的逻辑结构相同。

两棵不同的二叉树

满二叉树和完全二叉树

为什么使用二叉树? 在有序数组中插入数据项太慢 在链表中查找数据项太慢 要是能有一种数据结构，既能像链表那样快速的插入和删除，那样就好了。 结合另外两种数据结构的优点：一种是有序数组，另一种是链表。在树中查找数据项的速度和在有序数组个查找一样快，并且插入数据项和删除数据项的速度也和链表一样。

7.2.2 二叉树抽象数据类型 数据集合：二叉树的结点集合，每个结点由数据元素和构造数据元素之间关系的指针组成。 操作集合： （1）双亲结点parent()： （2）左孩子结点leftChild() （3）右孩子结点rightSibling() （4）左插入结点insertLeftNode(x) （5）右插入结点insertRightNode(x)： （6）左删除子树deleteLeftTree() （7）右删除子树deleteRightTree() （8）遍历二叉树traverse(vs)

二叉树的性质 性质1 若二叉树的层次从0开始, 则在二叉树的第 i 层最多有 2i 个结点。(i  0) [证明用数学归纳法] 归纳假设：对所有j（1<=j<i）,j层上的最大结点数为2i. 归纳步骤：根据归纳假设，第i-1层上的最大结点数为2i-1，故第i层上的最大结点数为2×2i-1=2i.命题成立。

性质2 深度为 h 的二叉树最多有 2h+1-1个结点。(h  -1) [证明用求等比级数前k项和的公式] 20 + 21 + 22 + … + 2h = 2h+1-1

性质3 对任何一棵二叉树, 如果其叶结点有 n0 个, 度为2的非叶结点有 n2 个, 则有 证明：若设度为1的结点有 n1 个，总结点个数为 n， 则有 n = n0 + n1 + n2 而度为1的结点有1个子女，度为2的结点有2个结点，叶子结点没有子女，根结点不是任何结点的子女，从子女结点数角度看，有 0×n+1×n + 2n2 +1 = n 因此，有 2n2 + n1 = n0 + n1 + n2 - 1 n2 = n0 - 1 n0 = n2 + 1

性质4 具有 n (n  0) 个结点的完全二叉树的深度为 log2(n+1) -1 证明：设完全二叉树的深度为 h，则有 2h - 1 < n  2h+1 - 1 变形 2h < n+1  2h+1 取对数 h < log2(n+1)  h+1 因此有 log2(n+1) = h+1 h = log2(n+1) -1 上面h层结点数 第h层结点数

性质5 如将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号0, 1, 2, …, n-1，则有以下关系： 若i = 0, 则 i 无双亲 若i > 0, 则 i 的双亲为(i -1)/2 若2*i+1 < n, 则 i 的左子女为 2*i+1，若2*i+2 < n, 则 i 的右子女为2*i+2 若 i 为偶数, 且i != 0, 则其左兄弟为i-1, 若 i 为奇数, 且i != n-1, 则其右兄弟为i+1 1 2 3 4 5 6 7 8 9

7.2.4 二叉树的存储结构 1 二叉树的顺序存储结构 非完全二叉树的顺序存储结构如下图

对于完全二叉树，用顺序存储结构存储时既能节省存储空间，又能使二叉树的操作实现非常简单。对于非完全二叉树，如果它接近于完全二叉树，即需要增加的空结点数目不多时，可采用顺序存储结构存储。 但是，对于非完全二叉树，如果需要增加的空结点数太多时，就不宜采用顺序存储结构存储。最坏的情况时右单支树，若右单支树采用顺序存储结构方法存储，则一棵深度为h的右单支树只有h个结点，却需要分配2h – 1个存储单元。

二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。 二叉链存储结构的每个结点包含三个域 。 leftChild data rightChild

二叉链存储结构的二叉树 （a）不带头结点的二叉树 （b）带头结点的二叉树

二叉树的二叉链式存储结构是一种常用的二叉树存储结构。其优点是结构简单，可以方便的构造任意需要的二叉树，key方便的实现二叉树的大多数操作。其缺点是查找当前节点的双亲结点操作实现起来比较麻烦。 另一种形式是三叉链。三叉链是在二叉链的基础之上再增加一个双亲结点域parent。三叉链对于查找当前结点的双亲结点操作实现起来比较容易。

3 二叉树的仿真指针存储结构 二叉树的仿真指针存储结构是用数组存储二叉树中的结点 。 二叉树的仿真二叉链存储结构

7.3 以结点类为基础的二叉树设计 7.3.1 二叉树结点类 7.3.2 二叉树的遍历 1 二叉树遍历的基本方法 7.3 以结点类为基础的二叉树设计 7.3.1 二叉树结点类 7.3.2 二叉树的遍历 1 二叉树遍历的基本方法 一棵二叉树由三部分组成：根结点、左子树和右子树 。 根据遍历算法访问根结点的次序，我们介绍三种遍历算法分别为前序遍历（DLR）、中序遍历（LDR）和后序遍历（LRD）。

前序遍历（DLR）递归算法为： 若二叉树为空则算法结束；否则： （1）访问根结点； （2）前序遍历根结点的左子树； （3）前序遍历根结点的右子树。 中序遍历（LDR）递归算法为： （1）中序遍历根结点的左子树； （2）访问根结点； （3）中序遍历根结点的右子树。

后序遍历（LRD）递归算法为： 若二叉树为空则算法结束；否则： （1）后序遍历根结点的左子树； （2）后序遍历根结点的右子树； （3）访问根结点。 除前序、中序和后序遍历算法外，二叉树还有层序遍历。层序遍历的要求是：按二叉树的层序次序（即从根结点层至叶结点层），同一层中按先左子树再右子树的次序遍历二叉树。

二叉树的层序遍历算法如下： （1）初始化设置一个队列； （2）把根结点指针入队列； （3）当队列非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出队列取得当前队头结点，访问该结点； （3.b）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入队列； （3.c）若该结点的右孩子结点非空，则将该结点的右孩子结点指针入队列； （4）结束。

7.3.3 二叉树遍历的应用 1 打印二叉树 2 查找数据元素

查找数据元素： 在二叉树中查找数据元素操作的要求是：在以t为根结点的二叉树中查找数据元素x，若查到数据元素x则返回该节点；若查找不到数据元素x时返回空。 在二叉树t中查找数据元素x函数可设计成前序遍历函数，即首先在根结点查找，然后在左子树查找，最后在右子树查找。 但是，和常规递归算法不同的是，此函数当一个分支上的结点比较完后，但仍未查找到数据元素x时，要返回到该结点的双亲结点处继续查找。因此，这是回溯算法的一个应用。

7.3.5 非递归的二叉树遍历算法 非递归的二叉树前序遍历算法如下： （1）初始化设置一个堆栈； （2）把根结点指针入栈； （3）当堆栈非空时，循环执行步骤（3.a）到步骤（3.c）； （3.a）出栈取得栈顶结点，访问该结点； （3.b）若该结点的右孩子结点非空，则将该结点的右孩子 结点指针入栈； （3.c）若该结点的左孩子结点非空，则将该结点的左孩子结点指针入栈； （4）结束。

对于上图所示的二叉树，非递归的二叉树前序遍历算法的执行过程 如下页图所示：

7.5 二叉树的分步遍历 二叉树的分步遍历是指，在规定了一棵二叉树的遍历方法后，每次只访问当前结点的数据元素值，然后使当前结点为当前结点的后继结点，直到到达二叉树的最后一个结点为止。 7.5.1 二叉树游标类 要满足分步遍历操作的需要，首先要有可分解的遍历算法，并要分解这样的遍历算法为几个子算法。然后再把这样的子算法设计成几个控制遍历过程的成员函数。这样，应用程序就可通过这几个成员函数，方便地对二叉树进行分步遍历操作。本节我们所讨论的就是这样的一种类，我们把它称作二叉树游标类。

由于二叉树遍历的具体方法有许多种，而每种遍历方法相应类的成员函数名都一样，因此我们先设计一个基类，再把二叉树中序（前序、后序、层序等）游标类设计为该基类的派生类。 一方面，对于派生类中共同的成员变量和成员函数可一次性设计完成；另一方面，由于各二叉树游标类都是基类派生类，所以其遍历的控制过程完全相同，从而可方便的使用和维护。

7.5.2 二叉树中序游标类 非递归的二叉树中序遍历算法如下： （1）设置一个堆栈并初始化； （2）使结点对象引用t等于二叉树根指针，如t非空令结束标记为0；否则为1； （3）当t的左孩子结点不空时循环；否则转向步骤（4）； （3.1）把t入堆栈； （3.2）t等于t的左孩子结点；

（4）如果t为空则令结束标记为1； （5）如果结束标记为1转步骤（8）；否则继续执行； （6）访问t结点； （7）如果t的右孩子结点非空，则使t等于t的右孩子结点，转到步骤（3）；否则如果堆栈不空，则退栈使t等于栈顶结点，转向步骤（5）；否则令结束标记为1，转向步骤（5）； （8）算法结束。

非递归的二叉树中序遍历算法执行过程

7.5.3 二叉树层序游标类 二叉树层序遍历的次序是根结点，根结点的左孩子结点，根结点的右孩子结点，根结点的左孩子结点的左孩子结点，根结点的左孩子结点的右孩子结点，如此等等，一直到最下层最右边的结点为止。 把它用在分步层序遍历二叉树上，需要把算法过程分解为几个子过程，由reset()成员函数、endOfBiTree()成员函数和next()成员函数来分别完成。 reset()成员函数完成使当前结点等于根结点 ； next()成员函数完成让当前结点等于当前结点的下一个结点。

7.6 线索二叉树 把结点中指向前驱结点和后继结点的指针称为线索。在二叉树的结点上加上线索的二叉树称作线索二叉树。对二叉树以某种方法（如前序、中序或后序方法）遍历使其变为线索二叉树的过程称作按该方法对二叉树进行的线索化。

线索化二叉树 (Threaded Binary Tree) 增加 Pred 指针和 Succ 指针的二叉树

线索化二叉树及其二叉链表表示 LeftChild data RightChild LeftThread RightThread LeftThread=0, LeftChild为左子女指针 LeftThread=1, LeftChild为前驱线索 RightThread=0, RightChild为右子女指针 RightThread=1, RightChild为后继指针

二叉树

中序线索二叉树

前序线索二叉树

后序线索二叉树

7.7 哈夫曼树 7.7.1 哈夫曼树的基本概念 在一棵二叉树中，定义从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径。 7.7 哈夫曼树 7.7.1 哈夫曼树的基本概念 在一棵二叉树中，定义从A结点到B结点所经过的分支序列叫做从A结点到B结点的路径。 从A结点到B结点所经过的分支个数叫做从A结点到B结点的路径长度 从二叉树的根结点到二叉树中所有叶结点的路径长度之和称作该二叉树的路径长度。

如果二叉树中的叶结点都带有权值，我们可以把这个定义加以推广。设二叉树有n个带权值的叶结点，定义从二叉树的根结点到二叉树中所有叶结点的路径长度与相应叶结点权值的乘积之和为该二叉树的带权路径长度（WPL），即： WPL = wi为第i个叶结点的权值，li为从根结点到第i个叶结点的路径长度。

具有相同叶结点和不同带权路径长度的二叉树 （a）WPL = 1×2+3×2+5×2+7×2 = 32 （b）WPL = 1×2+3×3+5×3+7×1 = 33 （c）WPL = 7×3+5×3+3×2+1×1 = 43 （d）WPL = 1×3+3×3+5×2+7×1 = 29

根据哈夫曼树的定义，要使一棵二叉树的带权路径长度WPL值最小，必须使权值越大的叶结点越靠近根结点。哈夫曼提出的构造哈夫曼树构造算法为： （1）由给定的n个权值{w1,w2,…,wn}构造n棵只有根 结点的二叉树，从而得到一个二叉树森林F={T1,T2,…,Tn}。 （2）在二叉树森林F中选取根结点的权值最小和次小的两棵二叉树作为新的二叉树的左右子树构造新的二叉树，新的二叉树的根结点权值为左右子树根结点权值之和。

（3）在二叉树森林F中删除作为新二叉树左右子树的两棵二叉树，将新二叉树加入到二叉树森林F中。 对于一组给定的叶结点，设它们的权值集合为{7,5,3,1}，按哈夫曼树构造算法对此集合构造哈夫曼树的过程如图所示。

7.7.2 哈夫曼编码问题 在数据通讯中，经常需要将传送的文字转换为二进制 字符0和1组成的二进制串，我们称这个过程为编码。 例如要传送的电文为ABACCDA 不同的编码方案

哈夫曼树可用于构造代码总长度最短的编码方案。具体构造方法如下： 设需要编码的字符集合为{d1,d2,…,dn}，各个字符在电文中出现的次数集合为{w1,w2,…,wn}，以d1,d2,…,dn作为叶结点，以w1,w2,…,wn作为各叶结点的权值构造一棵二叉树，规定哈夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称之为哈夫曼编码。

哈夫曼编码

7.7.3 哈夫曼编码的软件设计 哈夫曼编码的数据结构设计 设计哈夫曼树的结点存储结构为双亲孩子存储结构。 weight flag parent leftChild rightChild 存放哈夫曼编码的存储结构为 start Bit[0] Bit[1] … Bit[maxBit-1]

7.8 树与二叉树的转换 1 树转换为二叉树 树转换为二叉树的方法是： （1）树中所有相同双亲结点的兄弟结点之间加一条连线。 7.8 树与二叉树的转换 1 树转换为二叉树 树转换为二叉树的方法是： （1）树中所有相同双亲结点的兄弟结点之间加一条连线。 （2）对树中不是双亲结点第一个孩子的结点，只保留新添加的该结点与左兄弟结点之间的连线，删去该结点与双亲结点之间的连线。 （3）整理所有保留的和添加的连线，使每个结点的第一个孩子结点连线位于左孩子指针位置，使每个结点的右兄弟结点连线位于右孩子指针位置。

树转换为二叉树的过程

2 二叉树还原为树 二叉树还原为树的方法是： （1）若某结点是其双亲结点的左孩子，则把该结点的右孩子、右孩子的右孩子……都与该结点的双亲结点用线连起来。 （2）删除原二叉树中所有双亲结点与右孩子结点的连线。 （3）整理所有保留的和添加的连线，使每个结点的所有孩子结点位于相同层次高度。

二叉树还原为树的过程

7.9 树的遍历 1 先根遍历 树的先根遍历递归算法为： （1）访问根结点； （2）按照从左到右的次序先根遍历根结点的每一棵子树。 7.9 树的遍历 1 先根遍历 树的先根遍历递归算法为： （1）访问根结点； （2）按照从左到右的次序先根遍历根结点的每一棵子树。 2 后根遍历 树的后根遍历递归算法为： （1）按照从左到右的次序后根遍历根结点的每一棵子树； （2）访问根结点。

先根遍历得到的结点序列为：A B E J F C G K L D H I 后根遍历得到的结点序列为：J E F B K L G C H I D A