有序序列折半查找如何构建判定树？
折半查找的过程看，可用二叉树来描述，二叉树中的每个结点对应有序表中的一个记录，结点中的值为该记录在表中的位置。通常称这个描述折半查找二叉树的过程称为折半查找判定树。
工具/原料
-
一个有序序列
-
方法/步骤
-
例如：长度为10的折半查找判定树的具体生成过程，都遵循左孩子结点<根结点<右孩子结点
-
在长度为10的有序表中进行折半查找，不论查找哪个记录，都必须和中间记录进行比较，而中间记录为（1+10）/2 =5 (注意要取整，即向下取整) 即判定数的的根结点为5。
-
考虑判定树的左子树，即将查找区域调整到左半区，此时的查找区间为[1,4],那么中间值为（1+4）/2 =2 (注意要取整) ，所以做孩子根结点为2
-
考虑判定树的右子树，即将查找区域调整到右半区，此时的查找区间为[6,10],那么中间值为（6+10）/2 =8 (注意要取整) ，所以做孩子根结点为8
-
重复以上步骤，依次去确定左右孩子
-
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！