二、二叉查找树的查找算法
在二叉查找树上进行查找的过程类似于次优查找树。
若二叉查找树为空，则查找不成功；否则
1）若给定值等于根结点的关键字，则查找成功；
2）若给定值小于根结点的关键字，则继续在左子树上进行查找；
3）若给定值大于根结点的关键字，则继续在右子树上进行查找。
从这几个例子可见，在二叉查找树中进行查找的过程为：从根结点出发，沿着左分支或右分支递归进行查询直至关键字等于给定值的结点；或者从根结点出发，沿着左分支或右分支递归进行查询直至子树为空树止。前者为查找成功的情况，后者为查找不成功的情况。算法描述如下。
先看几个例子。
算法 9.5bool SearchBST (BSTree T, KeyType kval, BSTree f, BSTree &p )
{
// 根指针T所指二叉查找树中递归查找关键字等于kval的数据元素,若查找成
// 功,则指针p指向该数据元素结点,并返回TRUE,否则指针p指向查找路径上访
// 问的最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL
if (!T) { p = f; return FALSE; } // 查找不成功
else if ( key == T->data.key )
{ p = T; return TRUE; } // 查找成功
else if ( key < T->data.key )
return SearchBST (T->lchild, key, T, p );
// 返回在左子树中继续查找所得结果
else return SearchBST (T->rchild, key, T, p );
// 返回在右子树中继续查找所得结果
} // SearchBST
需要注意的是，算法中的引用参数指针 p 在算法结束时的状态。若查找成功，即二叉查找树中存在等于给定值的关键字，则 p 指向该关键字所在结点，正如学员在上页的演示中所看到的；若查找不成功，则 p 应该指向查找路径上最后一个结点。请看下列演示例子。