数据结构(二叉排序树)

roseying 2020-05-11

二叉排序树

插入,删除和查找的效率都比较高(创建时与二叉树相同)

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

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

查找:二叉树的中序遍历(从小到大)

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

删除:

  • 如果待删除的是叶子结点:直接删除即可
  • 若待删除结点只有左孩子或者右孩子,则直接将子树接到双亲的位置上(代替删除结点即可)
  • 带删除的结点左右子树都存在:
  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);
}

平衡二叉树

相关推荐