從折半查找的過(guò)程看，以有序表的中間記錄作為比較對(duì)象，并以中間記錄將表分割為兩個(gè)子表，對(duì)子表繼續(xù)上述操作。所以，對(duì)表中每個(gè)記錄的查找過(guò)程，可用二叉樹(shù)來(lái)描述，二叉樹(shù)中的每個(gè)結(jié)點(diǎn)對(duì)應(yīng)有序表中的一個(gè)記錄，結(jié)點(diǎn)中的值為該記錄在表中的位置。通常稱這個(gè)描述折半查找過(guò)程的二叉樹(shù)為折半查找判定樹(shù)。

長(zhǎng)度為n的折半查找判定樹(shù)的構(gòu)造方法為：

⑴ 當(dāng)n=0時(shí)，折半查找判定樹(shù)為空；

⑵ 當(dāng)n＞0時(shí)，折半查找判定樹(shù)的根結(jié)點(diǎn)是有序表中序號(hào)為mid=(n+1)/2的記錄，根結(jié)點(diǎn)的左子樹(shù)是與有序表r[1] ~ r[mid-1]相對(duì)應(yīng)的折半查找判定樹(shù)，根結(jié)點(diǎn)的右子樹(shù)是與r[mid+1] ~ r[n]相對(duì)應(yīng)的折半查找判定樹(shù)。

例如，長(zhǎng)度為10的折半查找判定樹(shù)的具體生成過(guò)程為：

⑴ 在長(zhǎng)度為10的有序表中進(jìn)行折半查找，不論查找哪個(gè)記錄，都必須先和中間記錄進(jìn)行比較，而中間記錄的序號(hào)為(1+10)/2=5（注意是整除即向下取整），即判定樹(shù)的根結(jié)點(diǎn)是5，如圖7-2(a)所示；

⑵ 考慮判定樹(shù)的左子樹(shù)，即將查找區(qū)間調(diào)整到左半?yún)^(qū)，此時(shí)的查找區(qū)間是

[1，4]，也就是說(shuō)，左分支上為根結(jié)點(diǎn)的值減1，代表查找區(qū)間的高端high，此時(shí)，根結(jié)點(diǎn)的左孩子是(1+4)/2=2，如圖7-2(b)所示；

⑶ 考慮判定樹(shù)的右子樹(shù)，即將查找區(qū)間調(diào)整到右半?yún)^(qū)，此時(shí)的查找區(qū)間是

[6，10]，也就是說(shuō)，右分支上為根結(jié)點(diǎn)的值加1，代表查找區(qū)間的低端low，此時(shí)，根結(jié)點(diǎn)的右孩子是(6+10)/2=8，如圖7-2(c)所示；

⑷ 重復(fù)⑵⑶步，依次確定每個(gè)結(jié)點(diǎn)的左右孩子，如圖7-2(d)所示。

對(duì)于折半查找判定樹(shù)，需要補(bǔ)充以下兩點(diǎn)：
⑴ 折半查找判定樹(shù)是一棵二叉排序樹(shù)，即每個(gè)結(jié)點(diǎn)的值均大于其左子樹(shù)上所有結(jié)點(diǎn)的值，小于其右子樹(shù)上所有結(jié)點(diǎn)的值；
⑵ 折半查找判定樹(shù)中的結(jié)點(diǎn)都是查找成功的情況，將每個(gè)結(jié)點(diǎn)的空指針指向一個(gè)實(shí)際上并不存在的結(jié)點(diǎn)——稱為外結(jié)點(diǎn)，所有外結(jié)點(diǎn)即是查找不成功的情況，如圖7-2(e)所示。如果有序表的長(zhǎng)度為n，則外結(jié)點(diǎn)一定有n+1個(gè)。 在折半查找判定樹(shù)中，某結(jié)點(diǎn)所在的層數(shù)即是查找該結(jié)點(diǎn)的比較次數(shù)，整個(gè)判定樹(shù)代表的有序表的平均查找長(zhǎng)度即為查找每個(gè)結(jié)點(diǎn)的比較次數(shù)之和除以有序表的長(zhǎng)度。例如，長(zhǎng)度為10的有序表的平均查找長(zhǎng)度為：
ASL=(1×1+2×2+3×4+4×3)/10=29/10
在折半查找判定樹(shù)中，查找不成功時(shí)的比較次數(shù)即是查找相應(yīng)外結(jié)點(diǎn)時(shí)與內(nèi)結(jié)點(diǎn)的比較次數(shù)。整個(gè)判定樹(shù)代表的有序表在查找失敗時(shí)的平均查找長(zhǎng)度即為查找每個(gè)外結(jié)點(diǎn)的比較次數(shù)之和除以外結(jié)點(diǎn)的個(gè)數(shù)。