二叉樹查詢問題

查詢二叉樹用折半查詢法，該方法優點是比較次數少，查詢速度快，平均效能好；其缺點是要求待查表為有序表。因此，折半查詢方法適用於不經常變動而查詢頻繁的有序列表。首先，假設表中元素是按升序排列，將表中間位置記錄的關鍵字與查詢關鍵字比較，如果兩者相等，則查詢成功；否則利用中間位置記錄將表分成前、後兩個子表，如果中間位置記錄的關鍵字大於查詢關鍵字，則進一步查詢前一子表，否則進一步查詢後一子表。重複以上過程，直到找到滿足條件的記錄，使查詢成功，或直到子表不存在為止，此時查詢不成功。