二叉排序树插入与删除.cpp

【实例简介】二叉排序树插入与删除
【实例截图】
【核心代码】#include <stdio.h>        
#include <stdlib.h>      
typedef int  Status;       
typedef int  KeyType;//关键字类型
typedef struct{
    KeyType key;//关键字
}TElemType;   

typedef struct BiNode{
    TElemType  data;//数据域
    struct BiNode  *lchild, *rchild;//左右结点指针
}BiNode,*BiTree;

Status CreateBST(BiTree &T){//二叉排序树的构建
    Status InsertBST(BiTree &T, TElemType e);//二叉排序树插入结点
    int num;//顶点总数
    TElemType e;     
    printf("请输入结点数：");
    scanf("%d", &num);    
    printf("请输入%d个整数\n", num);
    for(int i = 0; i < num; i ) {
        scanf("%d", &e.key);
        InsertBST(T, e);}    
    printf("二叉排序树创建完成\n");
    return 1;
}

Status PrintElement(KeyType key){
    printf(" %d ", key);
    return 1;
}

Status InOrderTraverse(BiTree T, Status(* Visit)(KeyType)){//中序遍历二叉树
    if(T){//根结点不为空
        if(InOrderTraverse(T->lchild, Visit)) {//访问左孩子
            if(Visit(T->data.key)) {//访问根结点
                if(InOrderTraverse(T->rchild, Visit)){//访问右孩子
                    return 1;}}}
        return 0;}
    else {return 1;}
}

Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p){//二叉排序树的查找
    if(!T){p = f;return 0;}   
    else if(key== T->data.key){p = T;return 1;}   
    else if (key< T->data.key){return SearchBST(T->lchild, key, T, p);} //递归地在左子树中继续查找
    else{return SearchBST(T->rchild, key, T, p);}//递归地在右子树中继续查找  
}

Status InsertBST(BiTree &T, TElemType e){//插入
    BiTree s, p;
    if(!SearchBST(T, e.key, NULL, p)){
        s = (BiTree)malloc(sizeof(BiNode));
        if(!s)  exit(0);
        s->data = e;
        s->lchild = s->rchild = NULL;       
        if(!p) T = s;
        else if (e.key< p->data.key) p->lchild = s;
        else p->rchild = s;
        return 1;}
    else return 0;          
}

Status Delete(BiTree &p){//删除结点
    BiTree q, s;
    if(!p->rchild){//若p右子树为空
        q = p;p = p->lchild;
        free(q);}//释放被存储空间
    else if(!p->lchild){//左子树为空
        q = p;p = p->rchild;
        free(q);}//释放被存储空间
    else{ //左右子树均不空
        q = p;s = p->lchild;
        while(s->rchild){
            q = s;s = s->rchild;}
        p->data = s->data;//s指向的结点变成了被删除结点
        if(q != p) q->rchild = s->lchild;
        else q->lchild = s->lchild;
        free(s);}  
    return 1;
}

Status DeleteBST(BiTree &T, KeyType key){    
    if(!T) return 0;//根结点为空，直接返回
    else{if(key== T->data.key){printf("删除关键字%d\n", key);
            if(Delete(T)){printf("删除成功！\n");
                return 1; }
            else{printf("删除失败\n");
                return 0;}}
        else if(key< T->data.key){return DeleteBST(T->lchild, key);}
        else return DeleteBST(T->rchild, key);    }
}

int main(){
    BiTree T = NULL, p = NULL;     
    KeyType key;
    Status flag;     
    TElemType e;
    char ch;
    char main[] = "1.构建一棵二叉排序树。\n"
                  "2.在二叉排序树中插入关键字\n"
                  "3.在二叉排序树中删除关键字\n"
                  "4.中序遍历二叉排序树\n"  
                  "5.退出程序\n";
    printf(main);
    while(1){ printf("请选择：");
        switch(ch = getchar(), ch){  
            case '1':{CreateBST(T);
                printf("中序遍历序列如下：");
                InOrderTraverse(T, PrintElement); break;}
            case '2':{if(!T){
                printf("二叉排序树还未建立。\n");break;}
                printf("输入想要插入的关键字：");
                scanf("%d", &e.key);
                flag=InsertBST(T, e);
                if(!flag) printf("插入失败！\n");
                else printf("插入成功！\n");
                printf("遍历序列如下：");
                InOrderTraverse(T, PrintElement);break;}
            case '3':{if(!T){
                printf("二叉排序树还未建立\n");break;}
                printf("输入想要删除的关键字：");
                scanf("%d", &key);
                DeleteBST(T, key);
                printf("中序遍历序列如下：");
                InOrderTraverse(T, PrintElement);break;}
            case '4':{printf("二叉排序树的中序遍历序列：");
                InOrderTraverse(T, PrintElement); break;}
            case '5':{exit(0);break;}
            }
        printf("\n");
        fflush(stdin);
    }        
    return 0;
}