二叉排序树.md

查找和插入比较简单。

删除操作比较复杂。

Status Delete(BiTree *p){
    BiTree q,s;
    if((*p)->rchild == NULL){
        //右子树空则只需要重接它的左子树
        q = *p;
        *p = (*p)->lchild;
        free(q);
    }
    else if((*p)->lchild == NULL){
        //左子树空，只需重连右子树
        q = *p;
        *p = (*p)->rchild;
        free(q);
    }
    else{
        //左右子树均不空
        q = *p;
        s = (*p)->lchild;
        while(s->rchild){//进入左子树，并向右（找比待删节点小且最接近的值，即直接前驱，用直接后驱替换也是类似的）
            q = s;  //q指向直接前驱的父节点
            s = s->rchild;
        }
        （*p)->data = s->data;   //s指向被删节点的直接前驱
        if(q != *p){
            q->rchild = s->lchild;  //重连q的右子树
        }
        else{//s->rchild为NULL
            q->lchild = s->lchild; //重连q的左子树
        }
        free(s);
    }
}