8.6.1　二叉排序树查找操作

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

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

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

  1. /* 递归查找二叉排序树T中是否存在key, */
  2. /* 指针f指向T的双亲，其初始调用值为NULL */
  3. /* 若查找成功，则指针p指向该数据元素结点，并
  4.    返回TRUE */
  5. /* 否则指针p指向查找路径上访问的最后一个结点
  6.    并返回FALSE */
  7. Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
  8. {
  9.     /* 查找不成功 */
  10.     if (!T)                                        
  11.     {
  12.         *p = f;
  13.         return FALSE;
  14.     }
  15.     /* 查找成功 */
  16.     else if (key == T->data)                       
  17.     {
  18.        *p = T;
  19.        return TRUE;
  20.     }
  21.     else if (key < T->data)
  22.         /* 在左子树继续查找 */
  23.         return SearchBST(T->lchild, key, T, p);    
  24.     else
  25.         /* 在右子树继续查找 */
  26.         return SearchBST(T->rchild, key, T, p);    
  27. }

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所示。

8.6.1　二叉排序树查找操作 - 图1

图8-6-4

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

8.6.1　二叉排序树查找操作 - 图2

图8-6-5

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

8.6.1　二叉排序树查找操作 - 图3

图8-6-6

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