算法 8.4.txt

数据结构各种算法原代码及图形示例

算法 8.4
bool Search_BST (BiTree T,  KeyType kval,  BiTree &p ,  BiTree &f ) 
{
      // 在根指针T所指二叉查找树中查找其关键字等于kval的数据元素，
      // 若查找成功，则指针p指向该数据元素结点，并返回TRUE，
      // 否则指针p指向查找路径上访问的最后一个结点，并返回FALSE,
      // 无论查找成功与否，f 总是指向 p 所指结点的双亲，其初始调用值为NULL
      p = T;                // p 指向树中某个结点，f指向其双亲结点
      while (p) { 
         if ( kval == p->data.key) 
           return TRUE;                             // 查找成功
         else  if ( kval < p->data.key) 
                  { f = p ;  p = p->lchild; }       // 在左子树中继续查找
               else  { f = p;  p = p->rchild; }     // 在右子树中继续查找
       } // while
      return FALSE;                                 // 查找不成功
} // SearchBST