本文目录一览：
折半查找的判定树怎么画
1.先画出满足有序表长度的最大满二叉树，然后将剩下的结点个数一个个插入该树；
2.从上往下看，比较每个结点的左右子树结点个数，如果左右子树结点个数相同优先放右边，左边比右边少就放左边，直到往下塞到二叉树底部成为叶子结点。
对于步骤1和2的具体做法，见下列实例分析：
长度为12的有序表画出折半查找判定树；
122^3，即最大能画出3层的满二叉树，接着将剩余5个结点插入该树；
先插入h，a的左右子树结点个数都为3，则到c，c的左右子树结点个数都为1，接着到g，g的左右子树都为0，最后h到了g的右边；
先插入i，a的左子树结点个数为3小于右子树的4，则到b，b的左右子树结点个数都为1，接着到e，e的左右子树都为0，最后i到了e的右边；
同理后面插入J，K，L折半查找判定树就完成了，如果要求各元素查找概率相同的情况下平均查找长度，则n=(1*1+2*2+4*3+5*4)/12=37/12。
折半查找的判定树怎么生成的？
按照比较的次数生成判定树，比较1次的是根结点，比较2次的在第二层，比较3次的在第三层，......一次类推，也可以说是每次的mid即形成判定树的结点，左子树上的结点是有序表前半部分的所有结点，右子树是后半部分的结点。
使用判定树进行描述时，应该从问题的文字描述中分清哪些是判定条件，哪些是判定的决策，根据描述材料中的联结词找出判定条件的从属关系、并列关系、选择关系，根据它们构造判定树。
扩展资料：
折半查找法的优点是比较次数少，查找速度快，平均性能好；其缺点是要求待查表为有序表，且插入删除困难。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
传统的加倍折半法主要应用于线段（或角）倍半关系的证明。随着“方法”的引申，其功能也随之得到了增强。它的用途远远超出了原先的范围，几乎适用于所有含“2”的类型题。下面，分“结论中含有2”和“题设中含有2”两中情况作简单的介绍。
计算机编程中经常使用到二分法进行比大小、数据查找等操作的程序编写，即将所需要进行处理的数据分成两部分，然后在其中一部分中进行类比查询，如果没有就将另一部分进行拆分，选其中一半进行查询，依次进行，直到得出结果；
分段查找法与此类似，先对数据进行拆分，然后根据处理能力对其中一部分进行查询，如果有，则查询结束，如果没有，对剩余部分进行继续拆分查找。
参考资料来源：百度百科--判定树
参考资料来源：百度百科--折半查找法
折半查找时若数据元素个数为偶数怎么画判定树
mid的位置就是(起点下标+ 终点下标)/2下取整
比如low = 1, high = 10, 因此mid = (1+10)/2 = 5
按照比较的次数生成判定树，比较1次的是根结点，比较2次的在第二层，比较3次的在第三层，......一次类推，也可以说是每次的mid即形成判定树的结点，左子树上的结点是有序表前半部分的所有结点，右子树是后半部分的结点。
扩展资料：
机器学习中，决策树是一个预测模型；他代表的是对象属性与对象值之间的一种映射关系。树中每个节点表示某个对象，而每个分叉路径则代表的某个可能的属性值，而每个叶结点则对应从根节点到该叶节点所经历的路径所表示的对象的值。
决策树仅有单一输出，若欲有复数输出，可以建立独立的决策树以处理不同输出。数据挖掘中决策树是一种经常要用到的技术，可以用于分析数据，同样也可以用来作预测。
参考资料来源：百度百科-决策树
对长度为10的有序表进行折半查找的判定树怎么画？
长度为n的折半查找判定树的构造方法为：
⑴ 当n=0时，折半查找判定树为空；
⑵ 当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。
题目中 长度为10的折半查找判定树的具体生成过程为：
⑴ 在长度为10的有序表中进行折半查找，不论查找哪个记录，都必须先和中间记录进行比较，而中间记录的序号为(1+10)/2=5（注意是整除即向下取整），即判定树的根结点是5，如图(a)所示；
⑵ 考虑判定树的左子树，即将查找区间调整到左半区，此时的查找区间是[1，4]，也就是说，左分支上为根结点的值减1，代表查找区间的高端high，此时，根结点的左孩子是(1+4)/2=2，如图(b)所示；
⑶ 考虑判定树的右子树，即将查找区间调整到右半区，此时的查找区间是[6，10]，也就是说，右分支上为根结点的值加1，代表查找区间的低端low，此时，根结点的右孩子是(6+10)/2=8，如图(c)所示；
⑷ 重复⑵⑶步，依次确定每个结点的左右孩子，如图(d)所示。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， website.service08@gmail.com 举报，一经查实，本站将立刻删除。
