首先我们提供一个二叉树的结构。

    1. /* 二叉树的二叉链表结点结构定义 */
    2. /* 结点结构 */
    3. typedef struct BiTNode{
    5.     /* 结点数据 */
    6.     int data;
    8.     /* 左右孩子指针 */
    9.     struct BiTNode *lchild, *rchild;
    10. } BiTNode, *BiTree;

    然后我们来看看二叉排序树的查找是如何实现的。

    1. /* 递归查找二叉排序树T中是否存在key, */
    2. /* 指针f指向T的双亲，其初始调用值为NULL */
    3. /* 若查找成功，则指针p指向该数据元素结点，并返回TRUE */
    4. /* 否则指针p指向查找路径上访问的最后一个结点并返回FALSE */
    5. Status SearchBST(BiTree T, int key, BiTree f, BiTree *p){
    7.     /* 查找不成功 */
    8.     if (!T){
    10.         *p = f;
    12.         return FALSE;
    13.     }
    14.     /* 查找成功 */
    15.     else if (key == T->data){
    17.         *p = T;
    18.         return TRUE;
    19.     }
    20.     else if (key < T->data)
    21.         /* 在左子树继续查找 */
    22.         return SearchBST(T->lchild, key, T, p);
    23.     else
    24.         /* 在右子树继续查找 */
    25.         return SearchBST(T->rchild, key, T, p);
    26. }
    1. SearchBST函数是一个可递归运行的函数，函数调用时的语句为SearchBST(T,93,NULL,p)，参数T是一个二叉链表，其中数据如图8-6-3所示，key代表要查找的关键字，目前我们打算查找93，二叉树f指向T的双亲，当T指向根结点时，f的初值就为NULL，它在递归时有用，最后的参数p是为了查找成功后可以得到查找到的结点位置。
    2. 第3～7行，是用来判断当前二叉树是否到叶子结点，显然图8-6-3告诉我们当前T指向根结点62的位置，T不为空，第5～6行不执行。
    3. 第8～12行是查找到相匹配的关键字时执行语句，显然93≠62，第10～11行不执行。
    4. 第13～14行是当要查找关键字小于当前结点值时执行语句，由于93>62，第14行不执行。
    5. 第15～16行是当要查找关键字大于当前结点值时执行语句，由于93>62，所以递归调用SearchBST(T->rchild,key,T,p)。此时T指向了62的右孩子88，如图8-6-4所示。

    image.png

    1. 此时第二层SearchBST，因93比88大，所以执行第16行，再次递归调用SearchBST(T->rchild,key,T,p)。此时T指向了88的右孩子99，如图8-6-5所示。

    image.png

    1. 第三层的SearchBST，因93比99小，所以执行第14行，递归调用SearchBST(T->lchild,key,T,p)。此时T指向了99的左孩子93，如图8-6-6所示。

    image.png

    1. 第四层SearchBST，因key等于T->data，所以执行第10～11行，此时指针p指向93所在的结点，并返回True到第三层、第二层、第一层，最终函数返回True。