数据结构（二叉排序树）

二叉排序树

插入，删除和查找的效率都比较高（创建时与二叉树相同）

二叉排序树又称为二叉排序树，若不为空树，则有以下性质：

• 若左子树不为空，则左子树上所有结点值均小于根节点的值
• 若右子树不为空，则右子树上所有结点值均小于根节点的值
• 他的左右子树也是二叉树排序树（递归）

查找：二叉树的中序遍历（从小到大）

插入：比根节点小的插入到二叉树根节点的左边，反之插入到右边

删除：

• 如果待删除的是叶子结点：直接删除即可
• 若待删除结点只有左孩子或者右孩子，则直接将子树接到双亲的位置上（代替删除结点即可）
• 带删除的结点左右子树都存在：

1. 用该节点直接前驱或直接后继来替换该结点（只用数据覆盖）
2. 用前驱的左子树代替前驱，用后继的右子树代替后继

• 如图可以看出要删除105的话，可以用他的前驱或者后替代他
• 前驱为104，需要注意的是他的前驱只有两种可能：为叶子结点或，或者只有左子树（用为如果有右子树的话那么105的前驱就是他的右子树了）
• 后继用同样的道理可以得出，后继108：为叶子结点，或只有右子树
• 所以删除一个结点时有两种方法：用前驱或后继的数据覆盖删除点的数据，用前驱的左子树接到前驱位置上，或用后继的右子树接到后继上
• 请思考这里如果100没有右子树时，105的前驱就是他的左子树，这时就不是将前驱的右子树接到前驱位置上了，而是将前驱的右左子树接到前驱位置上

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
typedef int ElemType;

typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild;//左孩子
    struct BiTNode *rchild;//右孩子
}BiTNode,* BiTree;

int Delete(BiTree *);

//递归查找二叉树T中是否存在key
//指针f指向T的双亲，其初始值调用值为NULL
//若查找成功，则指针p指向该数据元素结点并返回1
//否则指针p指向查找路径上访问的最后一个结点，返回0
int SearchBST(BiTree T,int key,BiTree f,BiTree *p){
    if(!T){//查找不成功
        *p=f;
        return 0;
    }else if(key==T->data){
        *p=T;
        return 1;
    }else if(key<T->data){
        return SearchBST(T->lchild,key,T,p);//在左子树继续查找
    }else{
        return SearchBST(T->rchild,key,T,p);//在右子树继续查找
    }
}

//当二叉排序树T中不存在关键字等于key的数据元素树
//插入key并返回1，否者返回0
int InsertBST(BiTree *T,ElemType key){
    BiTree p,s;
    if(!SearchBST(*T,key,NULL,&p)){
        s=(BiTree)malloc(sizeof(BiTNode));
        s->data=key;
        s->lchild=s->rchild=NULL;
        if(!p){//查找不到key
            *T=s;
        }else if(key<p->data){
            p->lchild=s;
        }else{
            p->rchild=s;
        }
        return 1;
    }else{
        return 0;//树中已有关键字相同的结点，不在插入
    }
}

void cenprintf(BiTree tree){
    if(tree){
        cenprintf(tree->lchild);
        printf("%d  ",tree->data);
        cenprintf(tree->rchild);
    }
}

int DeleteBST(BiTree *T,int key){
    if(!*T){
        return 0;
    }else{
        if(key==(*T)->data){
            return Delete(T);
        }else if(key<(*T)->data){
            return DeleteBST(&(*T)->lchild,key);
        }else{
            return DeleteBST(&(*T)->rchild,key);
        }
    }
}

int 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是双亲结点
            //s:用于寻找删除结点左子树上最右边的结点（值最大的结点）（删除结点的前驱结点）
            q=s;
            s=s->rchild;
        }
        (*p)->data=s->data;
        //如果q==p:表明while语句循环体没有执行，即删除结点的前驱就是它的左孩子
        //如果前驱是它的左孩子，就说明他前驱没有右孩子；就要把左孩子接到原前驱位置上
        //否者表示前驱不为删除结点的左孩子，那么他可能有左孩子，一定没有右孩子，所以把前驱左孩子接到原前驱位置上
        if(q != *p){
            q->rchild=s->lchild;
        }else{
            q->lchild=s->lchild;
        }
        free(s);
    }
    return 1;
}

void main(){
    ElemType val;
    BiTree tree=(BiTree)malloc(sizeof(BiTNode));
    tree->data=5;
    tree->lchild=tree->rchild=NULL;
    printf("请输入插入树的值：");
    scanf("%d",&val);
    while(-1!=val){
        InsertBST(&tree,val);
        printf("请输入插入树的值：");
        scanf("%d",&val);
    }
    cenprintf(tree);
    printf("\n请输入删除结点：");
    scanf("%d",&val);
    DeleteBST(&tree,val);
    cenprintf(tree);
}

平衡二叉树