t_search.c

《数据结构》教材源程序,可以让你轻松的根据教材学习数据结构

/****************************************************/
/*  基于二叉排序树的检索算法   文件名：t_search.c   */
/*          函数名：bssearch1()、bssearch2()        */
/****************************************************/

/*-------二叉排序树的非递归查找-------*/
void bssearch1(bstree t,datatype x, bstree *p,bstree *q)
 { /* q返回待查结点x在二叉排序树中的地址，p返回待查结点x的父结点地址 */
   *p=NULL;
   *q=t;
   while (*q)
      {
       if (x==(*q)->key) return;
       *p=*q;
       *q=(x<(*q)->key)? (*q)->lchild:(*q)->rchild;
      }
   return;
}
/*-------二叉排序树的递归查找-------*/
bstree bssearch2(bstree t,datatype x)
 { /*在二叉排序树t中查找关键字为x的结点，若找到则返回该结点的地址，否则返回NULL*/
   if (t==NULL || x==t->key)
       return t;
   if (x<t->key)
       return bssearch2(t->lchild,x);   /*递归地在左子树中检索*/
   else
       return bssearch2(t->rchild,x);   /*递归地在右子树中检索*/

 }