你是要算法還是本題答案?
本題答案為
10
8 16
5 12 20
7 19
算法為：
步驟：若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字,成功.
否則,若小于根結(jié)點(diǎn)的關(guān)鍵字值,遞歸查左子樹(shù).
若大于根結(jié)點(diǎn)的關(guān)鍵字值,遞歸查右子樹(shù).
若子樹(shù)為空,查找不成功.
平均情況分析（在成功查找兩種的情況下）
在一般情況下,設(shè) P（n,i）且它的左子樹(shù)的結(jié)點(diǎn)個(gè)數(shù)為 i 時(shí)的平均查找長(zhǎng)度.如圖的結(jié)點(diǎn)個(gè)數(shù)為 n = 6 且 i = 3; 則 P（n,i）= P（6,3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6
= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意：這里 P(3)、P(2) 是具有 3 個(gè)結(jié)點(diǎn)、2 個(gè)結(jié)點(diǎn)的二叉分類樹(shù)的平均查找長(zhǎng)度.在一般情況,P（i）為具有 i 個(gè)結(jié)點(diǎn)二叉分類樹(shù)的平均查找長(zhǎng)度.P(3) = （1+2+2）/ 3 = 5/3
P(2) = （1+2）/ 2 = 3/2
∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
n
二叉樹(shù)
-1
∴ P（n）= ∑ P（n,i）/ n