查詢不成功就是從查詢位置開始直到一個位置為空需要比較的次數。
比如：
62
/ \
30 74
15 56
/
48
找到所有的外結點，也就是查詢失敗的點，然後計算ASL
就你的BST，結果如下：
15的左右子樹都為空，也就是左右子樹都是外結點，失敗時需要比較62、30、15一共3次
48的左右子樹都為空，也就是左右子樹都是外結點，失敗時需要比較62、30、15、48一共4次
56的右子樹為空，也就是右子樹是外結點，失敗時需要比較62、30、56一共3次
74的左右子樹都為空，也就是左右子樹都是外結點，失敗時需要比較62、74一共2次
因此外結點總數為2 *3 + 1 = 7 （其實這個數量一定是關鍵字個數加1）
所以ASL = (2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) / 7 = 21 / 7 = 3。
擴充套件資料：
查詢步驟：
二叉樹
若根結點的關鍵字值等於查詢的關鍵字，成功。否則，若小於根結點的關鍵字值，遞迴查左子樹。若大於根結點的關鍵字值，遞迴查右子樹。若子樹為空，查詢不成功。
平均情況分析（在成功查詢兩種的情況下）：
在一般情況下，設 P（n，i）為它的左子樹的結點個數為 i 時的平均查詢長度。如圖的結點個數為 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 個結點、2 個結點的二叉分類樹的平均查詢長度。 在一般情況，P（i）為具有 i 個結點二叉分類樹的平均查詢長度。平均查詢長度= 每個結點的深度的總和 / 總結點數
查詢不成功就是從查詢位置開始直到一個位置為空需要比較的次數。
比如：
62
/ \
30 74
/ \
15 56
/
48
找到所有的外結點，也就是查詢失敗的點，然後計算ASL
就你的BST，結果如下：
15的左右子樹都為空，也就是左右子樹都是外結點，失敗時需要比較62、30、15一共3次
48的左右子樹都為空，也就是左右子樹都是外結點，失敗時需要比較62、30、15、48一共4次
56的右子樹為空，也就是右子樹是外結點，失敗時需要比較62、30、56一共3次
74的左右子樹都為空，也就是左右子樹都是外結點，失敗時需要比較62、74一共2次
因此外結點總數為2 *3 + 1 = 7 （其實這個數量一定是關鍵字個數加1）
所以ASL = (2 * 3 + 2 * 4 + 1 * 3 + 2 * 2) / 7 = 21 / 7 = 3。
擴充套件資料：
查詢步驟：
二叉樹
若根結點的關鍵字值等於查詢的關鍵字，成功。否則，若小於根結點的關鍵字值，遞迴查左子樹。若大於根結點的關鍵字值，遞迴查右子樹。若子樹為空，查詢不成功。
平均情況分析（在成功查詢兩種的情況下）：
在一般情況下，設 P（n，i）為它的左子樹的結點個數為 i 時的平均查詢長度。如圖的結點個數為 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 個結點、2 個結點的二叉分類樹的平均查詢長度。 在一般情況，P（i）為具有 i 個結點二叉分類樹的平均查詢長度。平均查詢長度= 每個結點的深度的總和 / 總結點數