数据结构__二叉搜索树

(1)二叉搜索树定义

/**树节点定义**/
typedef struct BitNode
{
int data;
struct BitNode *lChild,*rChild;
}BiTNode,*BiTree;

/***二叉树的搜索**/
//递归查找二叉树T中的Key是否存在,用指针f指向T的双亲，若查找成功则指针p指向该数据元素节点
//若失败，则指针指向路径上访问的最后一个节点，并返回false,也就是插入数据的位置
bool searchBST(BiTree T,int Key,BiTree f,BiTree *p)
{

    if(!T)
    {
    *p = f;
    return false;
    }
       
    else if(Key== T->data)
    {
    *p = T;
    return true;
    }
    else
    {
    return searchBST(Key<T->data?T->lChild:T->rChild,Key,T,p);
    }
}

/* 插入节点 */
bool insertBST(BiTree *T,int Key)
{
BiTree p,s;
if(!searchBST(*T,Key,NULL,&p))//找插入位置p
{
    s = (BiTree) new BiTNode;
    s->data = Key;
    s->lChild = s->rChild = NULL;
    if(!p)//如果插入的事第一个节点
       *T = s;
    else if(Key< p->data)
        p->lChild =s;
    else
        p->rChild =s;
    return true;
}
else
    return false;
}

//查找删除节点的位置
bool deleteBST(BiTree  *T,int Key)
{
   if(!*T)
    return false;
   else
    {
    if（Key==(*T)->data）
        return  Delete(T);
    else if(Key<(*T)->data)
        return DeleteBST(&(*T)->lChild,Key);
    else
        return DeleteBST(&(*T)->rChild,Key);
    }
}

//具体删除节点操作
//分两种情况考虑，一种情况，就是删除的节点 只有左子树或者右子树，或者啥都没有 这种操作是一样的
//另外一种情况是左右子树都有，当我们找到删除节点的时候，要从其右子树找到一个值最小的节点和当前节点的值交换，然后再删除这个节点 因为这样可以满足删除该节点的二叉树依然是二叉排序树
bool Delete（BiTree * p）
{
BiTree q,s;
if(（*p）->rChild==NULL)
{
q = *p;
 p =  (*p)->lChild;
delete q;
}
else if((*p)->lChild==NULL)
{
  q = *p;

p = (*p)->lChild ;
delete q;
}
else
{
q=*p;
s = p->rChild;
while(s->lChild)
{
q= s;
s = s->lChild;
}
(*p)->data = s->data;//值的替换

if(q!=*p)
   q->rChild = s->lChild;
 else
    q->lChild =s->lChild;
delete s;
}






}