Question

折半查找的判定树怎么生成的？

Answer 1

按照比较的次数生成判定树，比较1次的是根结点，比较2次的在第二层，比较3次的在第三层，......一次类推，也可以说是每次的mid即形成判定树的结点，左子树上的结点是有序表前半部分的所有结点，右子树是后半部分的结点。

使用判定树进行描述时，应该从问题的文字描述中分清哪些是判定条件，哪些是判定的决策，根据描述材料中的联结词找出判定条件的从属关系、并列关系、选择关系，根据它们构造判定树。

扩展资料：

折半查找法的优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。

传统的加倍折半法主要应用于线段（或角）倍半关系的证明。随着“方法”的引申，其功能也随之得到了增强。它的用途远远超出了原先的范围，几乎适用于所有含“2”的类型题。下面，分“结论中含有2”和“题设中含有2”两中情况作简单的介绍。

计算机编程中经常使用到二分法进行比大小、数据查找等操作的程序编写，即将所需要进行处理的数据分成两部分，然后在其中一部分中进行类比查询，如果没有就将另一部分进行拆分，选其中一半进行查询，依次进行，直到得出结果；

分段查找法与此类似，先对数据进行拆分，然后根据处理能力对其中一部分进行查询，如果有，则查询结束，如果没有，对剩余部分进行继续拆分查找。

参考资料来源：百度百科--判定树

参考资料来源：百度百科--折半查找法