查找 - 樹上的查找 - 二叉排序樹（四）

　　() 二叉排序樹上的查找

　　①查找遞歸算法

　　在二叉排序樹上進行查找和二分查找類似也是一個逐步縮小查找范圍的過程

　　遞歸的查找算法

　　BSTNode *SearchBST(BSTree TKeyType key)

　　{ //在二叉排序樹T上查找關鍵字為key的結點成功時返回該結點位置否則返回NUll

　　if(T==NULL||key==T>key) //遞歸的終結條件

　　return T; //T為空查找失敗;否則成功返回找到的結點位置

　　if(keykey)

　　return SearchBST(T>lchildkey);

　　else

　　return SearchBST(T>rchildkey);//繼續在右子樹中查找

　　} //SearchBST

　　②算法分析

　　在二叉排序樹上進行查找時若查找成功則是從根結點出發走了一條從根到待查結點的路徑若查找不成功則是從根結點出

　　發走了一條從根到某個葉子的路徑

　　() 二叉排序樹查找成功的平均查找長度

　　在等概率假設下下面(a)圖中二叉排序樹查找成功的平均查找長度為

　　

　　在等概率假設下(b)圖所示的樹在查找成功時的平均查找長度為

　　ASL b =(+++++++++)/=

　　

　　注意

　　與二分查找類似和關鍵字比較的次數不超過樹的深度

From:http://tw.wingwit.com/Article/program/sjjg/201311/23814.html