资源简介

(共93张PPT)
第4章 树
树的基本概念
二叉树
二叉树的遍历实现
赫夫曼树
特殊的树
树的基本概念
二叉树
二叉树的遍历实现
4.2
4.3
4.1
点击查看本小节知识架构
点击查看本小节知识架构
点击查看本小节知识架构
赫夫曼树
4.4
点击查看本小节知识架构
特殊的树
4.5
点击查看本小节知识架构
学习目标
掌握
掌握
熟练
掌握
掌握树的基本概念
1
熟练编写二叉树的操作代码
4
2
掌握二叉树的基本概念
3
掌握二叉树的遍历方式
前面的章节介绍的都是线性结构，其数据元素之间采用的都是一对一的关系。本章将主要介绍数据结构中的一种非线性结构——树。树形结构在文件系统与数据库开发中应用十分普遍，可以用来提高数据排序和检索的效率。二叉树作为树形结构的一种特殊形式，无论是应用于开发，还是作为基础学习的对象，都具有重要的研究意义。因此，本章将围绕二叉树的性质以及具体操作进行深入讲解，最后介绍一些特殊树形结构的概念以及设计原理。
4.1 树的基本概念
4.1.1
树的定义
返回目录
4.1.2
树的基本术语
4.1.1 树的定义
1.2.1节介绍数据的逻辑结构时，已经对树形结构进行了简单的说明，树形结构是一种非线性结构，其数据元素之间存在一对多的关系。
树（Tree）是N（N≥0）个结点的有限集合，它满足以下4个条件。
（1）有且只有一个特定的被称为根（Root）的结点。
（2）除了根结点，其余每个结点都有且只有一个直接前驱。
（3）每个结点都可以有多个后继，没有后继的结点称为叶结点（树叶）。
（4）除了根结点，其他结点可以分为m（m≥0）个互不相交的有限集合T1、T2……Tm，其中每一个集合又可以视为一棵树，称为根的子树（SubTree）。
4.1.1 树的定义
树形结构如图所示。
4.1.1 树的定义
图中，T1、T2、T3是根结点A的子树，同时T4是结点B的子树，T5是结点D的子树。需要特别注意的是，树形结构中的子树没有个数限制，但是它们之间一定不相交。图所示为两种不符合定义的子树。
4.1.2 树的基本术语
1.度数
一个结点的子树（或后继结点）的个数称为该结点的度数。度数为0的结点称为叶结点或终端结点，度数不为0的结点称为分支结点，除根结点以外的分支结点称为内部结点。一棵树的度数指的是该树中结点的最大度数。如图所示。
4.1.2 树的基本术语
图中，结点A、B、D都有自己的子树，即度数不为0，都是分支结点，且结点B、D为内部结点；结点C、E、F、G、H没有子树，即度数为0，都是终端结点。图中结点D的度数最大（度数为3），因此该树的度数为3。
2.结点关系
结点的子树的根（结点的后继结点）称为该结点的孩子（Child），同时该结点称为孩子结点的双亲结点（父结点），具有同一双亲结点的孩子结点互相称为兄弟结点。
图中，结点B的孩子结点为结点D和结点E，换句话说，结点B是结点D与结点E的双亲结点，结点B与结点C互为兄弟结点。
4.1.2 树的基本术语
3.结点层次
树也可以被视为一种层次结构，树中的每个结点都在固定的层次上。结点层次从根结点开始定义，根结点的层次为1，其孩子结点的层次为2，以次类推。树中结点的最大层次称为树的深度（Depth）或高度。如图所示。
由图可知，该树的深度为4，结点A处于第1层，结点B、C处于第2层，结点D、E处于第3层，结点F、G、H处于第4层。
4.有序树与无序树
兄弟结点有顺序（不可交换）的树称为有序树，兄弟结点无顺序的树称为无序树。
4.2 二叉树
4.2.1
二叉树的概念
返回目录
4.2.2
满二叉树
4.2.3
完全二叉树
4.2.4
二叉树的性质
4.2 二叉树
4.2.5
二叉树的存储
返回目录
4.2.6
二叉树的遍历方式
4.2.1 二叉树的概念
二叉树是一种特殊的树形结构，其中的每一个结点最多只能有两个直接后继。二叉树的递归定义如下。
（1）有且只有一个根结点。
（2）可以是空树，当为非空树时，它由一个根结点以及两棵互不相交且分别称为左子树和右子树的二叉树组成。
二叉树的任意结点最多只有两棵子树，也可以没有子树或者只有一棵子树，因此二叉树的度数一定小于或等于2。二叉树严格区分左右子树，即使只有一棵子树也要区分左右。
综上所述，二叉树具有以下5种基本形态。
（1）空二叉树。
（2）只有一个根结点。
（3）一个根结点和根结点的左子树构成。
（4）一个根结点和根结点的右子树构成。
（5）一个根结点和根结点的左右子树构成。
4.2.2 满二叉树
满二叉树每层的结点数都是最大结点数，除了最后一层为叶结点，其余所有结点都有左右子树。深度为k的满二叉树有2 k -1个结点，如图所示。
4.2.2 满二叉树
满二叉树是一种理想状态，所有的叶结点都在同一层中。如果一颗二叉树除了叶结点，其他结点都有左右子树，但叶结点不在同一层，则这颗二叉树并不是满二叉树，如图所示。
由图可知，同样深度的二叉树，满二叉树的结点数最多，叶结点数也最多。
4.2.3 完全二叉树
对一棵具有n个结点的二叉树的结点按层序进行编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树的中编号为i（1≤i≤n）的结点位置相同，那么该树就是完全二叉树。如图所示。
图（a）与图（c）中，相同编号的结点位置相同，因此图（a）中的树符合完全二叉树的条件，而图（b）与图（c）中，树的第5号和6号结点位置不相同，因此图（b）所示的树不符合完全二叉树的条件。
4.2.4 二叉树的性质
1.性质1
二叉树的第i（i≥1）层中最多有 2 i-1 个结点。图所示的满二叉树中，第3层结点的个数为2 3-1=4个，第4层结点的个数为 2 4-1=8个。
2.性质2
深度为k的二叉树最多有 2 k-1个结点。在同等深度的二叉树中，满二叉树的结点数最多，叶结点数最多。
3.性质3
在任何一棵二叉树中，如果叶结点的数量为N，度数为2的结点数量为N 2，则N=N 2+1。假设该树中度数为1的结点数量为 N 1 ，则这棵树的总结点数为 N+N 1 +N 2 ，总结点数也可以是所有子结点数加1（根结点）的和，即 N 1 +2×N 2 +1。因此N 1 +2×N 2 +1=N+N 1 +N 2 ，得出 N=N 2 +1。
4.2.5 二叉树的存储
1.二叉树的顺序存储
使用顺序存储实现二叉树就是用一维数组存储二叉树中所有的结点，并通过数组的下标体现结点在二叉树中的位置。图（a）中的完全二叉树在数组中的存储形式如图所示。
而对于非完全二叉树来说，如果将不存在的结点表示为“^”，则图（b）中的非完全二叉树在数组中的存储形式如图所示。
4.2.5 二叉树的存储
一棵深度为k的二叉树，需要分配2 k -1个存储单元的空间。如果该树为右斜树，那么采用顺序存储时将会浪费大量空间，如图所示。
由图可知，k值越大，浪费的存储空间越多。因此，顺序存储一般只用于完全二叉树。
4.2.5 二叉树的存储
2.二叉树的链式存储
在顺序存储不适用的情况下，可以考虑使用链式存储。使用链式存储表示二叉树，其结点结构与双向循环链表一致，即一个数据域和两个指针域，如图所示。这样的链表称为二叉链表。
图中，data为数据域，用来保存结点的数据，lchild与rchild为指针域，保存的是指向左右孩子的指针。二叉树链式结构如图所示。
4.2.6 二叉树的遍历方式
二叉树的遍历方式有很多，主要有以下4种。
1.先序遍历
先序遍历就是先访问根结点，然后访问其左孩子，最后访问其右孩子，其余子结点都遵循“根左右”的规则。也就是说，对树中的任意一个结点，都是先访问该结点的数据，然后访问其左孩子，最后访问其右孩子。先序遍历的访问顺序如图所示。
图中，按照先序遍历的规则，先访问结点A，再访问结点B，由于结点B又可以看作结点A左子树的根，按照“根左右”的访问顺序，下一次访问的结点应该是D，而不是C。
4.2.6 二叉树的遍历方式
根据上述遍历思想，采用先序遍历访问图中结点的顺序为A-B-D-H-I-E-C-F-J-G。
2.中序遍历
中序遍历就是先访问根结点的左孩子，然后访问根结点，最后访问根结点的右孩子，其余子结点都遵循“左根右”的规则。中序遍历的访问顺序如图所示。
图中，结点A的左孩子为结点B，结点B的左孩子为结点D，结点D的左孩子为结点H，因此采用中序遍历时，最先访问的结点应该是H。
采用中序遍历访问结点的顺序为H-D-I-B-E-A-J-F-C-G。
4.2.6 二叉树的遍历方式
3.后序遍历
后序遍历就是先访问左孩子，然后访问右孩子，最后访问根结点，其余子结点都遵循“左右根”的规则。后序遍历的访问顺序如图所示。
图中，采用后序遍历访问结点的顺序为H-I-D-E-B-J-F-G-C-A。
4.2.6 二叉树的遍历方式
4.层序遍历
层序遍历与前3种方式不同，其访问从树的第一层开始，从上到下逐层遍历，同一层中按照从左到右的顺序访问结点。层序遍历的访问顺序如图所示。
上述4种遍历方式的本质区别是访问结点的顺序不同。而对于计算机而言，它们是4种不同规则的线性序列，程序按照规则处理数据，可以应用于某些特定的场合。
4.3 二叉树的遍历实现
4.3.1
二叉树的定义
返回目录
4.3.2
二叉树的创建
4.3.3
二叉树的遍历
4.3.4
整体测试
4.3.1 二叉树的定义
二叉树中的结点结构与链表类似，代码如下所示。
以上代码中的两个指针分别用于指向该结点的左右子树，具体可参考图4.12。
4.3.2 二叉树的创建
创建二叉树需要考虑该二叉树是完全二叉树还是非完全二叉树。
1.完全二叉树的创建
如果对一棵有n个结点的完全二叉树的结点按层序进行编号，则对任意一个结点i（1≤i≤n）来说，有如下规律。
（1）如果i=1，则结点i无双亲，为根结点。
（2）如果i＞1，则结点i的双亲结点是结点i/2。
（3）如果 2i≤n，则结点i的左孩子是结点2i，否则结点i为叶结点。
（4）如果 2i+1≤n，则结点i的右孩子是结点2i+1，否则结点i无右孩子。
根据上述规律，通过代码实现创建完全二叉树，示例代码参考教材4.3.2节。
4.3.2 二叉树的创建
例中的代码使用了递归调用的思想，其原理如图所示。
例通过每一轮的函数递归调用，判断是否需要创建结点的左右孩子，如果无左右孩子，直接将指针指向NULL。
4.3.2 二叉树的创建
2.非完全二叉树的创建
完全二叉树的规律不适用于非完全二叉树，通过代码实现创建非完全二叉树，示例代码参考教材4.3.2节。
例同样使用了递归调用，与例4-1不同的是，程序允许用户选择是否创建结点的左右孩子。如果输入符号#，则当前创建不成立，直接返回NULL（即结点指针指向为空）。输出结果如下所示。
运行程序，手动输入q##，表示该树只有一个根结点，无左右子树，根结点的数据为q。
4.3.3 二叉树的遍历
1.先序遍历
先序遍历遵循“根左右”的规则，其代码实现使用了递归调用的思想，具体代码如下所示。
4.3.3 二叉树的遍历
以上代码输出结点的数据后，判断该结点是否有左右孩子（顺序不可互换），如果有则递归调用函数本身继续向下遍历。无论遍历到哪一个结点，都遵循“根左右”的访问顺序。
假设存在一棵非完全二叉树，如图所示。
使用上面的代码对图中的二叉树进行先序遍历，具体过程如下。
（1）第1次调用pre_order函数时，参数为指向结点A的指针，因此root不为NULL，执行printf()函数输出结点A的数据，然后判断结点A是否具有左孩子（判断为是），递归调用pre_order()函数（第2次调用）。
（2）第2次调用pre_order()函数时，参数为指向结点A左孩子（即结点B）的指针，因此root不为NULL，执行printf()函数输出结点B的数据，然后判断结点B是否具有左孩子（判断为是），递归调用pre_order()函数（第3次调用）。
4.3.3 二叉树的遍历
（3）第3次调用pre_order()函数时，参数为指向结点B左孩子（即结点D）的指针，因此root不为NULL，执行printf()函数输出结点D的数据，然后判断结点D是否具有左孩子（判断为是），递归调用pre_order()函数（第4次调用）。
（4）第4次调用pre_order()函数时，参数为指向结点D左孩子（即结点G）的指针，因此root不为NULL，执行printf()函数输出结点G的数据，然后判断结点G是否具有左孩子（判断为否），继续判断结点G是否具有右孩子（判断为否）。递归到此开始返回，返回到第3次调用pre_order()函数。
（5）返回到第3次调用pre_order()函数，继续判断结点D是否有右孩子（判断为否），返回到第2次调用pre_order()函数。
（6）返回到第2次调用pre_order()函数，继续判断结点B是否有右孩子（判断为是），调用pre_order()函数（第5次调用）输出结点E的数据，并且判断结点E是否有左右孩子（判断为否）。
（7）返回到第1次调用pre_order()函数，继续判断结点A是否有右孩子（判断为是），调用pre_order()函数（第6次调用），参数为指向结点A右孩子（即结点C）的指针，执行printf()函数输出结点C的数据，然后判断结点C是否有左孩子（判断为是），递归调用pre_order()函数（第7次调用）。
4.3.3 二叉树的遍历
（8）第7次调用pre_order()函数时，参数为指向结点C左孩子（即结点F）的指针，执行printf()函数输出结点F的数据，并且判断结点F是否有左右孩子（判断为否）。递归到此开始返回，返回到第6次调用pre_order()函数。
（9）返回到第6次调用pre_order()函数，继续判断结点C是否有右孩子（判断为否），返回到第1 次调用pre_order()函数。至此，程序运行结束。
4.3.3 二叉树的遍历
2.中序遍历
中序遍历遵循“左根右”的规则，其代码实现同样使用了递归调用的思想，具体代码如下所示。
4.3.3 二叉树的遍历
以上代码先判断结点是否有左孩子，然后输出结点数据，再判断结点是否有右孩子（顺序不可互换）。如果有左右孩子则递归调用函数本身继续向下遍历。无论遍历到哪一个结点，都遵循“左根右”的访问顺序。（具体过程可参考先序遍历）
3.后序遍历
后序遍历遵循“左右根”的规则，其代码实现同样使用了递归调用的思想，具体代码如下所示。
4.3.3 二叉树的遍历
以上代码先判断结点是否有左孩子，然后判断结点是否有右孩子，最后输出结点数据（顺序不可互换）。如果有左右孩子则递归调用函数本身继续向下遍历。无论遍历到哪一个结点，都遵循“左右根”的访问顺序。（具体分析可参考先序遍历）
4.层序遍历
二叉树的层序遍历可以利用队列的思想，从第一个结点（根结点）开始入队，然后出队，判断此结点是否有左孩子或右孩子。如果存在则继续入队，入队后继续执行之前的步骤。读者可参考3.6节的链式队列操作函数或例3-8来测试层序遍历的代码，具体代码参考教材4.3.3节。
4.3.4 整体测试
1.完全二叉树测试
使用创建完全二叉树的功能代码（例4-1），结合先序遍历、中序遍历、后序遍历的功能代码进行测试，示例代码参考教材4.3.4节。
根据第 96 行代码可知，创建一棵完全二叉树，且结点数为10，该二叉树的逻辑结构如图所示。
4.3.4 整体测试
由图可知，该二叉树采用先序遍历的顺序为1-2-4-8-9-5-10-3-6-7，中序遍历的顺序为8-4-9-2-10-5-1-6-3-7，后序遍历的顺序为8-9-4-10-5-2-6-7-3-1。
程序输出结果如下所示，参照上述推导结果，查看结点与数据是否对应。
根据输出结果可知，结点与数据一一对应，测试代码正确。
2.非完全二叉树测试
使用创建非完全二叉树的功能代码（例4-2），结合先序遍历、中序遍历、后序遍历的功能代码进行测试，示例代码参考教材4.3.4节。
4.3.4 整体测试
例需要用户自行输入二叉树的结点数据（按照创建非完全二叉树的代码逻辑思维输入），输入内容为ABD#G###CE##F##（符号#表示不存在该结点，详见第15行代码），与其对应的非完全二叉树的逻辑结构如图所示。
由图可知，该二叉树先序遍历的顺序为A-B-D-G-C-E-F，中序遍历的顺序为D-G-B-A-E-C-F，后序遍历的顺序为G-D-B-E-F-C-A。
运行程序并输入结点数据，其输出结果如下所示，参照上述推导结果，查看结点与数据是否对应。
遍历输出的结果与推导结果一致，测试代码正确。
4.4 赫夫曼树
4.4.1
赫夫曼树的概念
返回目录
4.4.2
赫夫曼树的原理
4.4.3
构造赫夫曼树
4.4.1 赫夫曼树的概念
赫夫曼树又称为最优二叉树。1952年，美国数学家赫夫曼（David Huffman）发明了一种压缩编码方法，为实现文件压缩，提高数据传输效率做出了重要贡献。为了纪念他的成就，将他在编码中使用的特殊二叉树称为赫夫曼树，同时将他的编码方式称为赫夫曼编码。
接下来通过一个例子引出赫夫曼树的概念。
在如今倡导素质教育的背景下，很多中小学已经取消使用百分制表示学科成绩的做法，而是使用优秀、良好、中等、及格和不及格来反应学生一个学期的整体成绩。对于老师来说，一般的做法是先通过评卷得到学生的成绩，再判断该成绩属于5个层次中的哪一个层次。以下代码实现了这样的转换。
4.4.1 赫夫曼树的概念
通常情况下，一个学校或年级中，大部分学生的成绩都处于中等以上。以上代码中，所有成绩都要先被判断是否及格，再逐级判断得到最终结果。因此，当成绩的输入量较大时，该算法存在很明显的效率问题。
用二叉树表示该算法，如图所示。
4.4.1 赫夫曼树的概念
假设通过计算得到学生成绩在5个层次范围的占比，如表所示。
由表可以看出，70分以上的成绩占总数80%，这些成绩在上述程序算法中都需要经过3次或3次以上的判断，显然该算法是不合理的。
由于中等成绩和良好成绩所占的比例较高，可以考虑对图所示的二叉树进行重新分配，如图所示。
4.4.1 赫夫曼树的概念
图所示的算法比图4.21效率要高，那么如何在一些特定的场合下设计出类似于图所示的二叉树（该方案在学生成绩这一场合中为最优算法），进而实现代码设计呢？，这就需要使用赫夫曼树的设计原理。
4.4.2 赫夫曼树的原理
对图所示的二叉树进行简化，如图所示。
对图所示的二叉树进行简化，如图所示。
4.4.2 赫夫曼树的原理
在图所示的二叉树中，A代表不及格，B代表及格，C代表中等，D代表良好，E代表优秀。这些结点对应的值为学生成绩占比。而赫夫曼树的定义中，树中每个结点的数据域可以存放一个特定的数值来，这个值称为权值。因此，将学生成绩占比作为结点的权值，得到结点A的权值为5，结点B的权值为15，结点C的权值为30，结点D的权值为40，结点E的权值为10。
在了解赫夫曼树的原理之前，需要先了解关于赫夫曼树的名词解释（结合图4.23和图4.24）。
（1）路径：在一棵树中，从一个结点到另一个结点之间的通路称为路径。图中，从根结点到结点C的通路就是一条路径。
（2）路径长度：一条路径中的分支数目称为路径长度，也就是说，在一条路径中，每经过一个结点，路径长度加1。图中，根结点到结点C的路径长度为3，根结点到结点D的路径长度为4。
（3）树的路径长度：从根结点到每一个结点的路径长度之和。图4.23所示的树的路径长度为1+1+2+2+3+3+4+4=20，图4.24所示的树的路径长度为1+2+3+3+2+1+2+2=16。
（3）结点的带权路径长度：从根结点到该结点的路径长度与该结点的权值的乘积。
4.4.2 赫夫曼树的原理
（4）结点的带权路径长度：树中所有叶结点的带权路径长度之和。
假设有n个权值{w 1 ,w 2 ,…,w n }，构造一棵有n个叶结点的二叉树，每个叶结点的权值为 w k，每个叶结点的的路径长度为 l k ，则该树的带权路径长度记作WPL= w k l k。其中带权路径长度WPL最小的二叉树称为赫夫曼树。
图所示的二叉树的WPL值为5×1+15×2+30×3+40×4+10×4=325。图所示的二叉树的WPL值为 5×3+15×3+30×2+40×2+10×2=220。如果学生成绩示例中有10000人，按照图4.23所示二叉树的判断方法，需要执行32500次比较，而按照图4.24所示二叉树的判断方法，需要执行22000次比较。很明显，采用第二种方式效率要比第一种高很多。
4.4.3 构造赫夫曼树
4.4.2节已经介绍了赫夫曼树的原理，接下来将讨论如何构建赫夫曼树。在构建赫夫曼树时，想要使树的带权路径长度最小，只需要遵循一个原则，权值越大的结点离树根越近。
假设有6个带权的结点，权值分别为9、12、6、3、5、15，将这些结点按照从小到大顺序进行排列，如图所示。
选出图中两个权值最小的结点，将这两个结点组成一个新的二叉树，且新二叉树的根结点的权值为左右孩子权值的和。如图所示。
4.4.3 构造赫夫曼树
在未组成树的剩余结点中选出权值最小的结点与二叉树合并，形成新的二叉树，如图所示。
此时新二叉树的根结点的权值为14，该值与未组成树的剩余结点的权值相差不大，且不是其中的最大值。因此可以继续从未组成树的剩余结点中选出权值最小的结点与二叉树合并，形成新的二叉树，如图所示。
4.4.3 构造赫夫曼树
此时新二叉树的根结点的权值为23，该值比剩余结点的权值大，且相差较大。因此二叉树不能继续组合，否则将不满足赫夫曼树的定义。
将剩余结点组合成新的二叉树，如图所示。
4.4.3 构造赫夫曼树
将图所示的两颗二叉树合并，生成最终的二叉树，此二叉树即为赫夫曼树。如图所示。
图所示的最终合并生成的二叉树就是赫夫曼树，该二叉树的带权路径长度WPL为12×2+15×
2+9×2+6×3+3×4+5×4=122。
4.5 特殊的树
4.5.1
二叉排序树
返回目录
4.5.2
平衡二叉树
4.5.3
B树
4.5.4
B+树与B*树
4.5.5
红黑树
4.5.1 二叉排序树
1.二叉排序树的定义
二叉排序树（Binary Sort Tree）又称为二叉搜索树（Binary Search Tree），其具体定义如下。
（1）若左子树不为空，则左子树上的所有结点的值小于根结点的值。
（2）若右子树不为空，则右子树上的所有结点的值大于根结点的值。
（3）左、右子树本身也是一棵二叉排序树。
由此定义可知，二叉排序树的左子树结点值<根结点值<右子树结点值。如果对二叉排序树进行中序遍历，可以得到一个递增的有序序列。如图所示，该二叉排序树中序遍历的顺序为1-2-3-4-5-6。
4.5.1 二叉排序树
2.二叉排序树插入结点
二叉排序树插入结点时，如果原二叉排序树为空，则直接插入该结点；如果该结点的值小于根结点的值，则将该结点插入左子树；如果该结点的值大于根结点的值，则将该结点插入右子树。
3.二叉排序树删除结点
二叉排序树删除结点时有以下3种情况。
（1）如果被删除的结点是叶结点，则直接删除，不会影响二叉树原有的规则。
（2）如果被删除的结点只有左子树或右子树，则将该结点的子树作为其双亲结点的子树，代替该结点；
（3）如果被删除的结点有左右子树，则可以根据中序遍历的结果，使用被删除结点的直接前驱或后继替换该结点。
4.5.1 二叉排序树
图所示的二叉排序树采用中序遍历访问结点的顺序为17-23-25-28-30-34-36-42-51。假设需要删除的结点是28，结点28的上一个遍历的结点为25，下一个遍历的结点为30。因此，选取这两个结点替换被删除的结点，即可完成删除操作，如图所示。
删除结点后，该二叉树仍然符合二叉排序树的规则。
4.5.1 二叉排序树
4.二叉排序树查找
在最坏的情况下，二叉排序树查找需要的时间取决于树的深度。假设某二叉排序树的结点个数为n，具体的查找分析如下。
（1）当二叉排序树接近于满二叉树时，其深度为 log 2 n，因此在最坏的情况下查找的时间复杂度为 O(log 2 n)。
（2）当二叉树形成单枝树时，其深度为n，在最坏的情况下查找的时间复杂度为O(n)。如图所示。
由此可知，为了保证二叉排序树有较高的查找速度，需要使该二叉排序树接近于满二叉树，即二叉排序树中的每一个结点的左、右子树深度尽量相等。
4.5.2 平衡二叉树
1.平衡二叉树的定义
由二叉排序树的查找分析可知，二叉排序树的查找效率与其形态有关。二叉排序树的形态最好是均匀的，这样就产生了平衡二叉树（Balanced Binary Search）。
平衡二叉树可以是空树，当其不为空树时，具有以下性质。
（1）左右子树的深度差的绝对值不超过1。
（2）左右子树也分别是平衡二叉树。
平衡二叉树中的左子树深度减去右子树深度的值称为平衡因子BF（Balance Factor）。因此，平衡二叉树上所有结点的平衡因子只能是-1、0、1。如果存在一个结点的平衡因子的绝对值大于1，那么该二叉树就不是平衡二叉树，如图所示。
4.5.2 平衡二叉树
平衡二叉树是一种特殊的二叉排序树，因此平衡二叉树应该满足二叉排序树的规则。图（a）为平衡二叉树，而图（b）不是平衡二叉树，原因是图（b）中二叉树根结点的值小于其左孩子。
2.构造平衡二叉树
俄罗斯数学家格奥尔基（Georgii M.Adelson-Velskii）和叶夫根尼（Evgenii M.landis）提出了一种动态保持平衡二叉树的方法。其基本思想是：在构造平衡二叉树时，每当插入一个结点时，先检查是否因插入结点而破坏树的平衡性，如果是，则找出其中最小不平衡子树，调整最小不平衡树中各结点的关系（在遵守二叉排序树规则的前提下），以达到新的平衡。
4.5.2 平衡二叉树
最小不平衡子树指的是距离新插入结点最近，以第一个平衡因子绝对值大于1的结点为根结点的子树。如图所示。
调整最小不平衡子树有以下4种情况。
（1）单向右旋，新结点插入位置为左子树的左子树，以左子树为轴心，进行单次向右旋转，如图所示。
4.5.2 平衡二叉树
由图可知，开始时结点3的BF为2（左子树深度减右子树深度），经过旋转后，结点2成为根结点，并且满足二叉排序树的规则。旋转后结点1、结点2、结点3的BF都为0。
（2）单向左旋，新结点插入位置为右子树的右子树，以右子树为轴心，进行单次向左旋转，如图所示。
由图可知，开始时结点1的BF为-2，经过旋转后，结点2成为根结点，结点1、结点2、结点3的BF都为0。
4.5.2 平衡二叉树
无论是单向左旋还是右旋，都可能出现一些复杂的情况，如图所示，开始时结点2的BF为-1，插入结点6后，结点2的BF变为-2，显然不满足平衡二叉树的规则。
对图所示的二叉树执行左旋操作，结点4将成为新的根结点，旋转后的二叉树如图所示。
4.5.2 平衡二叉树
如图所示，结点3原本是结点4的左孩子，为了在旋转后依然满足二叉排序树的规则，结点3变成了结点2的右孩子。
（3）双向旋转，先右后左，新结点插入位置为右子树的左子树，如图所示。
图中，新插入结点为结点8，插入结点8后，结点4的BF值变为-2，不满足平衡二叉树的规则。按照一般的做法，将结点6、结点10、结点8向左旋转，旋转后可以发现，结点8成为结点10的右孩子，8小于10，不符合二叉排序树的规则。
4.5.2 平衡二叉树
上述情况下，应该先将结点8、结点10向右旋转，如图所示。
图所示为旋转后得到的二叉树，再将结点6、结点8、结点10向左旋转，如图所示。
4.5.2 平衡二叉树
（4）双向旋转，先左向右，新结点插入位置为左子树的右子树，如图所示。
图中，当结点8插入后，结点6的BF为-2，结点4的BF为-2，不满足平衡二叉树的规则。直接以结点6为轴心进行旋转，并不能使该二叉树达到平衡，首先以结点9为轴心向右旋转。按照单向右旋的方式，旋转后的二叉树如图所示。
4.5.2 平衡二叉树
然后，将该二叉树以结点6为轴心向左旋转，如图所示。
如图所示，经过两次旋转后的得到二叉树为平衡二叉树。
4.5.3 B树
1.B树的定义
B树（B-tree）与平衡二叉树类似，不同的是，B树是一种平衡的多路查找树（结点的孩子至少有两个，且每个结点可以存储多个数据元素）。
数据库中的索引（索引存在于索引文件中，保存在磁盘中，帮助数据库高效获取数据）通常会使用该树形结构。当数据库索引非常大（数据量越大，索引文件越大），达到几个GB时，无法一次性加载到内存，而是逐一加载每一个磁盘页（对应树的结点）。然而磁盘读写的速度相对于内存来说是很慢的，为了减少二者吞吐量相差太多造成的系统消耗，比较好的办法是减少磁盘读写的次数。
当使用树形结构作为索引时，每一个结点对应一个磁盘页，减少磁盘读写次数就是缩减树的高度。因此，B树“矮胖”的特征，使其更适合作为数据库的索引，其结点最大的孩子数量称为B树的阶，其大小取决于磁盘页的大小。
4.5.3 B树
一个M阶的B树具有以下5个特征。
（1）非叶结点最多只有M个孩子，且M>2。
（2）除根结点以外的非叶结点都有k个孩子和k-1个数据元素，k值满足[M/2]。
（3）每一个叶结点都有k-1个数据元素，k值满足[M/2]。
（4）所有叶结点都在同一层次。
（5）所有分支结点的信息数据一致(n,A 0 ,K 1 ,A 1 ,K 2 ,A 2, …K n ,A n )，其中：K i (i=1,2,…n)为关键字，且K i ＜K i+1 (i=1,2,…n－1)；A i 为指向孩子结点的指针，且指针 A i-1 指向子树中的所有结点的关键字均小于 K i ，A n ，所指子树中的所有结点的关键字均大于 K n ；n为关键字的个数[M/2]－1≤n≤M－1）。
4.5.3 B树
图所示为插入9个数据后形成的B树。
4.5.3 B树
2.B树插入结点的实现
定义一棵5阶的B树（平衡5路查找），需要插入的结点数据为3、8、31、11、23、29、50、28。当前需要组成一棵5路查找树，则M=5，分支结点关键字的个数必须满足≤4。具体实现过程如下。
（1）先存入数据3、8、31、11，变化过程如图所示。（省略结点中表示关键字个数的表示n与指针 A i 。）
4.5.3 B树
图中，存入4个数据的结点已经满足5阶，因此再存入数据时，需要对该结点进行拆分。拆分的规则是将中间的数据元素提取到双亲结点上，该数据元素左边的数据元素单独形成一个结点，右边的数据元素单独形成一个结点。
（2）再存入数据23，变化过程如图所示。
4.5.3 B树
（3）再存入数据29，所有的结点都未达到5阶，不用拆分结点，如图所示。
（4）再存入数据50，结点达到5阶，如图所示。
4.5.3 B树
（5）最后存入数据28，由于结点已经达到5阶，此次存入数据需要拆分结点，如图所示。
3.B树删除结点的实现
假设当前存在一棵5阶的B树，如图所示。
4.5.3 B树
假设当前需要删除结点中的数据28，由B树的定义可知，结点的关键字数必须大于等于[5/2] ，因此删除数据28将导致结点不符合B树的规则。为了使删除数据后的结点依然满足B树的规则，在删除数据时需要将结点进行合并。
图中，如果删除结点中的数据28，首先需要将其双亲结点中的数据提取到该结点。提取后的结果如图所示。
4.5.3 B树
图中，数据29替换了数据28的位置，原来的双亲结点只剩余一个数据，不满足B树的规则，此时需要将数据39提取到双亲结点，如图所示。
4.5.4 B+树与B*树
1.B+树
B+树是B树的升级版，一棵完整的B+树具有以下特点。
（1）有k个子树的分支结点包含有k个元素，每个元素不保存数据，只用来作索引，所有数据都保存在叶结点。
（2）叶结点在B+树的最底层（所有叶结点都在同一层），叶结点中存放索引值、指向记录的指针、指向下一个叶结点的指针。叶结点按照关键字的大小，从小到大顺序链接。
（3）所有分支结点的元素都同时存在于子结点中，并且在子结点中是最大或最小的元素。
创建一棵完整的B+树，如图所示。（为了更加清晰地展示B+树的结点，图中分支结点忽略指针部分，特此说明。）
4.5.4 B+树与B*树
由图可知，B+树中的结点之间存在重复的元素，同时每一个叶结点都有指针指向右边的下一个叶结点，形成一个有序的链表。根结点的最大元素（图中为17）也是整个B+树的最大元素，无论插入或删除多少元素，始终要保持最大元素在根结点中。
需要注意的是，B+树中只有叶结点包含数据，其余分支结点只作为索引，没有任何数据关联，如图所示。
4.5.4 B+树与B*树
B+树的优势主要体现在查询性能上，在查询单个元素时，B+树会从根结点向下逐层查找，最终匹配到叶结点。假设当前需要查询图中的数据元素7，则一共需要3次磁盘页的读写来完成，如图所示。
4.5.4 B+树与B*树
由图可知，虽然B+树与B树的查找流程类似，但是B+树的分支结点不保存数据，同样大小的磁盘页，B+树可以存放更多的元素。也就是说，数据量相同的情况下，B+树的结构比B树更加“矮胖”，查询数据时磁盘读写的次数更少。
在B+树中查询数据必须查找到叶结点，而在B树中，数据元素可以存在于分支结点，也可以存在于叶结点，这导致B树的查找性能并不稳定（最坏的情况是查找到叶结点，最好的情况是查找根结点）。相反，B+树每一次查找都是稳定的。
如果查找为范围查找，则B+树的优势会更加明显。假设当前存在一棵完整的B树，如图所示，采用中序遍历，查找数据元素3到11。
4.5.4 B+树与B*树
由图可知，对B树进行范围查找是比较烦琐的。而B+树在进行范围查找时，只需要对链表直接做遍历。如图所示。
在B+树中，先查数据元素为3、5的结点，再查找数据元素为6、8的结点，最后查找数据元素为9、11的结点，遍历结束。显然，在链表中直接顺序遍历要比B树的中序遍历简单。
4.5.4 B+树与B*树
2.B*树
B*树是B+树的变体，B*树不同于B+树的是：其非根和非叶结点上增加了指向兄弟结点的指针。因此，对于一个M阶的B*树来说，非叶结点的关键字个数至少为(2/3)*M。
对于B+树来说，当一个结点满时，将分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在双亲结点中增加新结点的指针。因此，B+树的分裂只影响原结点和双亲结点，而不会影响兄弟结点（不需要指向兄弟的指针）。
而对于B*树来说，当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点中插入关键字，最后修改双亲结点的兄弟结点的关键字（因为兄弟结点的关键字范围发生改变）。如果兄弟结点已满，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在双亲结点中增加新结点的指针。
4.5.5 红黑树
红黑树（Red Black Tree）是一种自平衡二叉查找树，又可以称为平衡二叉B树（Symmetric binary B-tree）。因此，红黑树和平衡二叉树类似，都是在进行插入和删除操作时通过特定的操作保持二叉排序树的平衡，从而获得较高的查找性能。红黑树的每个结点上都有存储位来表示结点的颜色，即红或者黑。
一棵完整的红黑树满足以下4条规则。
（1）每个结点或者是黑色，或者是红色。
（2）每个叶结点都是黑色（叶结点都为NIL或NULL），根结点是黑色。
（3）如果一个结点是红色的，则它的子结点必须是黑色的。
（4）任意一个结点到其叶结点的路径都包含数量相同的黑结点。
根据上述最后一个规则可以推导出：如果一个结点存在黑子结点，那么该结点肯定有两个子结点。
4.5.5 红黑树
上述规则使得红黑树可以达到自平衡的状态，如图所示。
4.5.5 红黑树
当对红黑树进行结点的插入或删除时，红黑树的平衡就会被破坏，此时就需要对该树进行调整，以达到新的平衡。例如，在图所示的红黑树中插入新结点，如图所示。
4.5.5 红黑树
图中，插入的新结点为21（红），结点21的双亲结点22同样为红，因此不满足红黑树的规则，即红结点的子结点必须为黑结点。实现红黑树平衡有两种方式，变色与旋转。
由图可知，新插入的结点21为红，因此需要改变结点22，使之变为黑，如图所示。（截取图所示的红黑树中需要操作的部分）。
4.5.5 红黑树
图中，修改结点22为黑后，其双亲结点25为黑，不满足红黑树的最后一条规则，因此需要改变结点25为红，如图所示。
图中结点25与结点27都为红，不满足红黑树的规则。再次修改结点27为黑，如图所示，完成修改后该截取的部分满足红黑树的规则。
4.5.5 红黑树
上述变色操作只解决了截取部分的规则问题。如图所示，整个红黑树仍然不满足规则。
4.5.5 红黑树
图中，结点17与结点25都为红，不满足红黑树的规则。如果选择修改结点17为黑，则结点13与结点17同为黑，依然不满足规则。因此，通过变色已经无法解决当前问题，需要结合旋转的方式。
红黑树的旋转操作可以参考4.5.2节中平衡二叉树的旋转操作，将图所示的红黑树以结点17为轴心向左旋转，如图所示。
4.5.5 红黑树
图中，旋转后结点17成为根结点，其左子树成为结点13的右子树。
根据红黑树的规则（根结点必须为黑），需要再次进行变色操作，将结点17变为黑，则结点13需要变为红，结点8需要变为黑，结点1与结点11需要变为红，结点6需要变为黑。如图所示。
4.5.5 红黑树
图中，经过变色处理后的红黑树仍然不满足规则。例如，结点13到其叶结点的路径经过的黑色结点数量不同。接下来，需要再次使用旋转的方式实现红黑树平衡。
将图所示的红黑树以结点8为轴心向右旋转，如图所示。
4.5.5 红黑树
对图所示的红黑树再次进行变色操作，结点8变为红，结点1与结点13变为黑，结点6与结点15变为红，如图所示。
图所示为满足规则的红黑树，可见该红黑树达到平衡状态。其他插入或删除结点的情况，可参考上述操作过程实现平衡。
本章小结
本章主要介绍了一种非线性数据结构——树。其中，重点介绍了二叉树的概念、性质以及具体的代码实现。读者需要重点掌握二叉树的特性并熟练编写二叉树的操作代码，尤其是二叉树的先序遍历、中序遍历以及后序遍历。本章最后介绍了一些常见的特殊树形结构，包括赫夫曼树、二叉排序树、平衡二叉树、红黑树以及系列B树。望读者理解这些特殊树形结构的概念以及设计原理，从而扩展视野，为处理复杂树形结构的开发奠定基础。

展开更多......

收起↑