《数据结构》中基于二叉排序树的查找与排序算法讲解

吐尔地·托合提

（新疆大学信息科学与工程学院，乌鲁木齐830046）

0 引言

查找和排序是日常生活及计算机软件设计中极为常用的，而且是最基本的两种运算。因此，查找和排序所使用存储结构及相应算法设计是数据结构与算法课程中重点讲解内容[1]。在数据结构中，查找表是一种逻辑结构，是由同一类型的数据元素构成的集合，其实现方法有顺序表和树表（二叉链表）两种存储表示。对于排序，也是在类似于查找表的集合中，按照关键码大小进行比较和移动，重新安排每一个数据元素（记录）在序列中的相应位置。

在教学中，我们系统讲解如何构造查找表，或如何在内存中存储待排序序列，不同存储表示（顺序的和链式的）相应的查找和排序算法思路，并分析各种算法的性能和优缺点，从而从知识层面上基本达到掌握各种查找与排序算法，对算法性能进行分析的基本能力的课程目标[2]。但是，在教学中发现，因为用有限的课时去讲授较多的排序和查找算法，出现“内容多，消化不良”现象[3]，从而从技能层面很难达到从知识中体会和掌握算法设计的思维方式及技巧，提高分析问题和解决问题能力的课程目标[4]。

本文以基于二叉树的查找和排序为例，形成课堂案例教学，通过讲解在二叉排序树的构造、查找和排序算法上的一些启发思路的知识点，一方面加深了学生对于二叉树的性质、存储结构、遍历，以及二叉树应用的理解和掌握，另一方面引导学生要认识到解决问题有多种方案可选，使分析问题和解决问题的能力得到了提升。

1 二叉排序树的结构

二叉排序树的一般定义为：或者是一棵空树，或者是具有下列性质的二叉树。①若左子树不空，则左子树上所有结点的值均小于根结点的值；②若右子树不空，则右子树上所有结点的值均大于根结点的值；③左右子树也都是二叉排序树。通常，二叉排序树以二叉链表为存储结构，我们可以设计每个结点有三个域，即数 据 域（data）、左 孩 子 域（l_child）和 右 孩 子 域（r_child）。因为，查找表是不会有重复关键字，因此以这种基本结点结构构造二叉排序树是可以满足静态或动态查找需求。但是，如果我们在二叉排序树上对于序列关键码进行排序，因为待排序序列中会出现重复关键码，这就与二叉排序树基本性质不符。针对这种情况，我们可以在结点结构中增加一个域（times），来记录关键码重复出现次数，再对二叉排序树生成算法进行相应改进。改进后二叉排序树结点结构如图1所示。

图1 二叉排序树结点结构

二叉排序树是在查找过程中逐步插入结点而生成，插入结点过程为：从空树开始，在二叉排序树中查找待插入关键字key，若查找失败，则在对应位置插入一个新结点，给数据域data赋key值，times被赋值为1；否则查找成功，表明待插入关键字已在表中，不插入新节点，对于被查找成功结点times值增1。

设数据元素的关键字序列为{23，44，6，17，58，17，39，44}，则经过一系列查找和插入操作过程，便可以构造出一棵如图2所示的二叉排序树

图2 二叉排序树二叉链表示意图

以上关键字序列中，17和44都是2次出现，在生成过程中对于第二次出现的关键字不插入新节点，就修改（增1）已被插入相同关键字结点的times值即可。

2 基于二叉排序树的查找和排序算法

二叉排序树是常用来进行查找，其静态查找性能接近于顺序表折半查找，而动态查找效率远远高于折半查找[5]。但是从二叉排序树的性质可知，若左孩子不空，则左孩子的值小于根结点的值；若右孩子不空，则右孩子的值大于根结点的值。所以，对于二叉排序树进行中序遍历，就可以得到一个有序序列。我们在二叉排序树的二叉链表基本结点结构中增加一个域，以这种结点结构构造的二叉排序树不仅仍然满足静态和动态查找，也符合进行基于二叉排序树的排序，因此将排序和查找都在二叉排序树上进行成为了可能。以下介绍本文基于二叉排序树的查找和排序算法。为了简单讨论，以下假设关键码为整形，而且只考虑关键码，暂不考虑数据元素其他数据项。

二叉排序树结点结构定义为：

2.1 二叉排序树的查找

算法在二叉排序树上查找数据域data等于key的结点，Root为根结点指针，若查找成功，则返回指向该结点的地址，指针q指向其父结点，若待查找的key在根结点中或Root为空树，则q为空；若找找失败，则返回空指针，此时q指向查找失败前的最后一个结点。

2.2 二叉排序树的生成

二叉排序树不是一次生成的，而是边查找边插入。当二叉排序树Root中不存在数据域data值等于待插入关键字key[i]的结点时，插入数据域data值为key的新结点；若查找成功，则修改被查找成功结点times值增1；待插入关键字序列存储在一个长度为n的整形数组key[]中。

2.3 二叉排序树的排序

从二叉排序树的性质可知，二叉排序树中以任意一结点为根的子树都为二叉排序树。树中结点关键字大小依次为左孩子、根、右孩子，所以对二叉排序树进行中序遍历，便可得到一个有序序列，从而达到对于序列进行升序排序的目的。在此，根据文本定义的结点结构和二叉排序树构造过程中的操作思路，对于二叉树中序遍历算法进行相应的改进，就能得到基于二叉树中序遍历的树表排序算法。

从算法描述可知，对于关键字序列{23，44，6，17，58，17，39，44}及图2所示对应二叉排序树，经过中序遍历排序得到有序序列{6，17，17，23，39，44，44，58}。

最后将以上3个算法在一个主函数中调用，就能实现对一个数据元素集合的存储、查找和排序。

3 结语

在《数据结构》课程教学中，我们按照教材内容安排讲述在不同存储表示情况下的典型算法，如，顺序表的查找、树表的查找、哈希表的查找等。关于排序，除了基数排序之外，都是基于顺序表的典型排序算法，没有安排讲解在同一个存储结构上既能查找又能排序的拓展内容。其实，我们对一组数据进行处理时，不仅需要查找，而且也需要排序。因此，通常的做法是，选一种合理的物理结构对数据进行存储后，以数据为中心编写一套算法，而不是为不同算法存储多分数据。

数据结构中，二叉排序树的查找以二叉链表为存储结构，其静态查找性能接近于顺序表折半查找，但动态查找效率远远高于折半查找。因此，本文选二叉排序树为数据表示方法，对其基本结点结构和生成方法进行相应的改进，在它已有的高效查找特性的基础上，再引入了基于二叉树遍历的排序方法，一方面，加深了学生对链式存储结构、二叉树及二叉链表的性质、遍历算法的理解和应用掌握程度，另一方面，培养了学生以数据为中心的分析问题、解决问题的技能。