二叉判定樹也叫二叉排序樹或者是壹棵空樹，或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於或等於它的根結點的值；
（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 個結點二叉分類樹的平均查找長度。平均查找長度= 每個結點的深度的總和 / 總結點數。
百度百科-二叉排序樹