二分查找判定树的构造方法研究及应用*

摘 要：通过对二分查找的算法进行分析，并结合二分查找判定树的特点，提出一种快速画出二分查找的判定树的方法。该方法较传统方法更加直观，学生更容易理解掌握，而且比传统方法速度更快、效率更高，通过实例验证了提出方法的有效性。

关键词：快速方法；二分查找；判定树

中图分类号：TP311 文献标识码：A DoI: 10.3969/j.issn.1003-6970.2012.04.006

【Abstract】through analyzing binary search algorithm, we propose a fast generation of binary search decision tree algorithm combining with the characteristic of binary search decision tree algorithm. the method not only more visualized but also faster speed and higher efficiency than traditional method. It is more easily for students to understand and grasp. Through an example the effectiveness of this method is verified.

【Key words】fast Method, Binary Search, Decision tree

0 引 言

在《数据结构》中画出对n个结点的有序表进行二分查找的判定树的常规方法是按照二分查找的思想，采用递归的方法，对整个有序表中的每个元素都进行一次二分查找，才能最终确定该判定树。其过程较为复杂，要进行大量的运算，而且容易出现错误。以下通过对二分查找的算法进行分析，找到了一种更为方便快捷的方法，这种方法从解决实际问题的角度出发，在只要求画出判定树，并解决相应问题时，是非常实用的。

1 常规方法

mid=(1+10)/2=5，根节点为5，此时的判定树如图1-a所示；

2.缩小范围对左子表（1，2，3，4）进行查找，确定其的根。low=1，high=4，则mid=(1+4)/2=2，根节点为2，此时的判定树如图1-b所示；

3.再缩小范围对子表（3，4）进行查找，确定其根。

（1）从一个结点开始，每次增加一个结点，使该树满足条件a，最终得到8个结点的判定树的形状图，如图2-（a-h）所示。

（2）假设图2-h按层编号A、B、C、D、E、F、G、H（图2-i），则中序遍历得DBEAFCGH

把遍历结果与有序表对比把判定树中的字母按上表替换即可。如图2-j所示。

（1）中国人民大学2001年考研试题第一题第2小题，在有序表A[1..12]中，采用二分查找算法等于A[12]的元素，所比较的元素下标依次为 。本题可以采用本文提出的方法，直接绘制判定树，如图3所示，从图中直接可以得出答案为6，9，11，12。

low=3，high=4，则mid=(3+4)/2=3，根节点为3此时的判定树如图1-c所示；

依此类推……直至所有元素都被查找过为止，如图1-d所示。

图3 12个结点的判定树

(2) 2010年全国硕士研究生入学考试计算机专业真题单项选择第9题已知一个长度为16的顺序表L，其元素按关键字有序排列，若采用折半查找法查找一个不存在的元素，则比较次数最多的是（ ），此题考察对折半查找最坏情况下的查找长度的理解，查找失败的过程就是从判定树的根结点到某个空指针结点的途径，16个结点的二分查找判定树如图4所示，从图中可以得出答案为5。查找失败最多比较次数不超过判定树的深度，也就是说n个结点的判定树的深度应该与n个结点的完全二叉树的深度相等，为2log1n +???，也可以计算出本题答案为5。

用该方法解决问题和原方法相比由于不用再对每个关键字都进行二分查找，不需要进行繁琐的计算，速度快，并减少了出错的几率，即使在有序表的结点很多的时候也能快速的画出其二分查找地判定树，从而节省了做题时间，而且结点的增加或减少只需在树最底层添加或把最后插入的结点删除即可，而不用重新构造该树。