注册 登录
编程论坛 数据结构与算法

平衡二叉树建立失败,大佬求解

Wuhaoran2002 发布于 2021-12-19 12:15, 1868 次点击
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define LH +1
#define EH 0
#define RH -1

typedef int Status;
typedef int RcdType;

typedef struct BBSTNode{
    RcdType data;
    int bf;
    struct BBSTNode *lchild,*rchild;
}BBSTNode,*BBSTree;


void R_Rotate(BBSTree p){
    BBSTree lc=p->lchild;
    p->lchild=lc->lchild;
    lc->lchild=p;
    p=lc;
}

void L_Rotate(BBSTree p){
    BBSTree rc=p->lchild;
    p->rchild=rc->lchild;
    rc->lchild=p;
    p=rc;
}

void RightBalance(BBSTree T)
{   
BBSTree rc,ld;
rc=T->rchild;
switch(rc->bf){
  case RH:
  T->bf=rc->bf=EH;L_Rotate(T);break;
  case LH:
  ld=rc->lchild;
  switch(ld->bf){
    case RH:T->bf=LH;rc->bf=EH;break;
    case EH:T->bf=rc->bf=EH;break;
    case LH:T->bf=EH;rc->bf=RH;break;
  }
  ld->bf=EH;
  R_Rotate(T->rchild);
  L_Rotate(T);
  break;
}
}

void LeftBalance(BBSTree &T)
{   
BBSTree lc,rd;
lc=T->lchild;
switch(lc->bf){
  case LH:
  T->bf=lc->bf=EH;R_Rotate(T);break;
  case RH:
  rd=lc->rchild;
  switch(rd->bf){
    case LH:T->bf=RH;lc->bf=EH;break;
    case EH:T->bf=lc->bf=EH;break;
    case RH:T->bf=EH;lc->bf=LH;break;
  }
  rd->bf=EH;
  L_Rotate(T->rchild);
  R_Rotate(T);
  break;
}
}

BBSTree InsertAVL(BBSTree T,RcdType e,Status taller){
    if(NULL==T){
        T=(BBSTree)malloc(sizeof(BBSTNode));
        T->data=e;
        T->bf=EH;T->lchild=NULL;T->rchild=NULL;taller=TRUE;
    }else if(e==T->data){
        taller=FALSE;
        return FALSE;
    }else if(e<T->data){
        if(!InsertAVL(T->lchild,e,taller))return FALSE;
        if(taller){
            switch(T->bf){
                case LH:LeftBalance(T);taller=FALSE;break;
                case EH:T->bf=LH;taller=TRUE;break;
                case RH:T->bf=EH;taller=FALSE;break;
            }
        }
    }else{
        if(!InsertAVL(T->rchild,e,taller))return FALSE;
        if(taller){
            switch(T->bf){
                case LH:T->bf=EH;taller=FALSE;break;
                case EH:T->bf=RH;taller=TRUE;break;
                case RH:RightBalance(T);taller=FALSE;break;
            }
        }
    }
    return T;
}

BBSTree CreateAVL(BBSTree T,int N[],int num){
    int i,t;
    T=NULL;
    if(N){
        for(i=0;i<num;i++){
            InsertAVL(T,N[i],t);
        }
    }
    return T;
}

Status DepthAVL(BBSTree T){
    int LD,RD;
    if(T==NULL)
    return 0;
    else
    {
        LD=DepthAVL(T->lchild);
        RD=DepthAVL(T->rchild);
        return (LD>=RD?LD:RD)+1;
    }
}

void PrintAVL(BBSTree T){
    BBSTNode p[100][100]={};
    int row,col;
    int i,j,k;
    if(T){
        printf("平衡二叉树如下所示");
        row=DepthAVL(T);
        col=pow(2,row)-1;
        p[0][0]=*T;
        for(i=1;i<row;j++){
            for(j=0;j<pow(2,i);j++){
                if(j%2==0){
                    if(p[i-1][j/2].lchild)
                    p[i][j]=*(p[i-1][j/2].lchild);
                }
                else{
                    if(p[i-1][j/2].rchild)
                    p[i][j]=*(p[i-1][j/2].rchild);
                }
            }
        }
        k=pow(2,row);
        for(i=0;i<row;i++){
            for(j=0;j<pow(2,i);j++){
                if(p[i][j].data)
                printf("%*s%2d%*s",k-1,"",p[i][j].data,k-1,"");
            }
            k=k/2;
            printf("\n");
        }
    }
    else
    printf("当前为空树\n");
}

Status DeleteAVL(BBSTree T,RcdType e,BBSTree p,BBSTree f,Status taller,int mark){
    BBSTree r;
    int tmp;
    if(!p)
    return ERROR;
    else{
        if(e<p->data){
            if(!DeleteAVL(T,e,p,p->lchild,taller,0))
            return ERROR;
            if(taller){
                switch(p->bf){
                    case EH:
                        p->bf=RH;
                        taller=FALSE;
                        break;
                    case RH:
                        if(!f)
                        RightBalance(T);
                        else
                        RightBalance(f->lchild);
                        taller=TRUE;
                        break;
                    case LH:
                        p->bf=EH;
                        taller=TRUE;
                        break;
                }
            }
        }
        else if(e>p->data){
            if(!DeleteAVL(T,e,p,p->rchild,taller,1))
            return ERROR;
            if(taller){
                switch(p->bf){
                    case EH:
                        p->bf=LH;
                        taller=FALSE;
                        break;
                    case LH:
                        if(!f)
                        LeftBalance(T);
                        else
                        LeftBalance(f->rchild);
                        taller=TRUE;
                        break;
                    case RH:
                        p->bf=EH;
                        taller=TRUE;
                        break;
            }
        }
    }
    else{
        if(p->lchild!=NULL&&p->rchild==NULL){
            if(!f)
            T=p->lchild;
            else{
                if(mark==0)
                f->lchild=p->lchild;
                else
                f->rchild=p->rchild;
            }
            free(p);
            p=NULL;
            taller=TRUE;
        }
        else if(p->lchild==NULL&&p->rchild!=NULL){
            if(!f)
            T=p->rchild;
            else{
                if(mark==0)
                f->lchild=p->rchild;
                else
                f->rchild=p->rchild;
            }
            free(p);
            p=NULL;
            taller=TRUE;
        }
        else if(p->lchild==NULL&&p->rchild==NULL){
            if(!f)
            T=NULL;
            else{
                if(mark==0)
                f->lchild=NULL;
                else
                f->rchild=NULL;
            }
            free(p);
            p=NULL;
            taller=TRUE;
        }
        else{
            r=p->lchild;
            while(r->rchild)
            r=r->rchild;
            tmp=r->data;
            taller=FALSE;
            if(!f)
            DeleteAVL(T,tmp,NULL,p,taller,mark);
            else{
                if(mark==0)
                DeleteAVL(f->lchild,tmp,NULL,p,taller,mark);
                else
                DeleteAVL(f->rchild,tmp,NULL,p,taller,mark);
            }
            p->data=tmp;
        }
    }
    return OK;
}
}

int main(){
    BBSTree T1=NULL;
    int taller;
    int i,t;
    //T1=MakeBBSTree();
    int N[12]={88,29,91,19,50,32,24,45,62,79,52,67};
    int num=12;
    CreateAVL(T1,N,num);
    PrintAVL(T1);
    while(1){
        printf("输入操作序号:1 查看T1,2 插入T1,3 删除T1,4 离开:\n");
        scanf("%d",&t);
        switch(t){
            case 1:PrintAVL(T1);break;
            case 2:
                printf("输入要插入的数字:\n");
                scanf("%d",&t);
                InsertAVL(T1,t,taller);
                PrintAVL(T1);
                break;
            case 3:
                printf("输入要删除的数字:\n");
                scanf("%d",&t);
                DeleteAVL(T1,t,NULL,T1,taller,0);
                PrintAVL(T1);
                break;
            case 4:
                exit(0);
                default:
                    printf("非法输入!\n");
                    break;
        }
    }
}
1 回复
#2
diycai2021-12-21 16:55
程序代码:
#include<stdlib.h>
#include<stdio.h>
#include<math.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define LH +1
#define EH 0
#define RH -1

typedef int Status;
typedef int RcdType;

typedef struct BBSTNode{
    RcdType data;
    int bf;
    struct BBSTNode *lchild,*rchild;
}BBSTNode,*BBSTree;


void R_Rotate(BBSTree p){
    BBSTree lc=p->lchild;
    p->lchild=lc->lchild;
    lc->lchild=p;
    p=lc;
}

void L_Rotate(BBSTree p){
    BBSTree rc=p->lchild;
    p->rchild=rc->lchild;
    rc->lchild=p;
    p=rc;
}

void RightBalance(BBSTree T)
{   
BBSTree rc,ld;
rc=T->rchild;
switch(rc->bf){
  case RH:
  T->bf=rc->bf=EH;L_Rotate(T);break;
  case LH:
  ld=rc->lchild;
  switch(ld->bf){
    case RH:T->bf=LH;rc->bf=EH;break;
    case EH:T->bf=rc->bf=EH;break;
    case LH:T->bf=EH;rc->bf=RH;break;
  }
  ld->bf=EH;
  R_Rotate(T->rchild);
  L_Rotate(T);
  break;
}
}

void LeftBalance(BBSTree &T)
{   
BBSTree lc,rd;
lc=T->lchild;
switch(lc->bf){
  case LH:
  T->bf=lc->bf=EH;R_Rotate(T);break;
  case RH:
  rd=lc->rchild;
  switch(rd->bf){
    case LH:T->bf=RH;lc->bf=EH;break;
    case EH:T->bf=lc->bf=EH;break;
    case RH:T->bf=EH;lc->bf=LH;break;
  }
  rd->bf=EH;
  L_Rotate(T->rchild);
  R_Rotate(T);
  break;
}
}

BBSTree InsertAVL(BBSTree *pT,RcdType e,Status taller){
    BBSTree T = *pT;
    if(NULL==T){
        T=(BBSTree)malloc(sizeof(BBSTNode));
        T->data=e;
        T->bf=EH;T->lchild=NULL;T->rchild=NULL;taller=TRUE;
    }else if(e==T->data){
        taller=FALSE;
        return FALSE;
    }else if(e<T->data){
        if(!InsertAVL(&T->lchild,e,taller))return FALSE;
        if(taller){
            switch(T->bf){
                case LH:LeftBalance(T);taller=FALSE;break;
                case EH:T->bf=LH;taller=TRUE;break;
                case RH:T->bf=EH;taller=FALSE;break;
            }
        }
    }else{
        if(!InsertAVL(&T->rchild,e,taller))return FALSE;
        if(taller){
            switch(T->bf){
                case LH:T->bf=EH;taller=FALSE;break;
                case EH:T->bf=RH;taller=TRUE;break;
                case RH:RightBalance(T);taller=FALSE;break;
            }
        }
    }
    *pT = T;
    return T;
}

BBSTree CreateAVL(BBSTree *T,int N[],int num){
    int i,t;
    *T=NULL;
    if(N){
        for(i=0;i<num;i++){
            InsertAVL(T,N[i],0);
        }
    }
    return *T;
}

Status DepthAVL(BBSTree T){
    int LD,RD;
    if(T==NULL)
    return 0;
    else
    {
        LD=DepthAVL(T->lchild);
        RD=DepthAVL(T->rchild);
        return (LD>=RD?LD:RD)+1;
    }
}

void PrintAVL(BBSTree T){
    BBSTNode p[100][100]={0};
    int row,col;
    int i,j,k;
    if(T){
        printf("平衡二叉树如下所示");
        row=DepthAVL(T);
        col=pow(2,row)-1;
        p[0][0]=*T;
        for(i=1;i<row;i++){
            for(j=0;j<pow(2,i);j++){
                if(j%2==0){
                    if(p[i-1][j/2].lchild)
                    p[i][j]=*(p[i-1][j/2].lchild);
                }
                else{
                    if(p[i-1][j/2].rchild)
                    p[i][j]=*(p[i-1][j/2].rchild);
                }
            }
        }
        k=pow(2,row);
        for(i=0;i<row;i++){
            for(j=0;j<pow(2,i);j++){
                if(p[i][j].data)
                printf("%*s%2d%*s",k-1,"",p[i][j].data,k-1,"");
            }
            k=k/2;
            printf("\n");
        }
    }
    else
    printf("当前为空树\n");
}

Status DeleteAVL(BBSTree T,RcdType e,BBSTree p,BBSTree f,Status taller,int mark){
    BBSTree r;
    int tmp;
    if(!p)
    return ERROR;
    else{
        if(e<p->data){
            if(!DeleteAVL(T,e,p,p->lchild,taller,0))
            return ERROR;
            if(taller){
                switch(p->bf){
                    case EH:
                        p->bf=RH;
                        taller=FALSE;
                        break;
                    case RH:
                        if(!f)
                        RightBalance(T);
                        else
                        RightBalance(f->lchild);
                        taller=TRUE;
                        break;
                    case LH:
                        p->bf=EH;
                        taller=TRUE;
                        break;
                }
            }
        }
        else if(e>p->data){
            if(!DeleteAVL(T,e,p,p->rchild,taller,1))
            return ERROR;
            if(taller){
                switch(p->bf){
                    case EH:
                        p->bf=LH;
                        taller=FALSE;
                        break;
                    case LH:
                        if(!f)
                        LeftBalance(T);
                        else
                        LeftBalance(f->rchild);
                        taller=TRUE;
                        break;
                    case RH:
                        p->bf=EH;
                        taller=TRUE;
                        break;
            }
        }
    }
    else{
        if(p->lchild!=NULL&&p->rchild==NULL){
            if(!f)
            T=p->lchild;
            else{
                if(mark==0)
                f->lchild=p->lchild;
                else
                f->rchild=p->rchild;
            }
            free(p);
            p=NULL;
            taller=TRUE;
        }
        else if(p->lchild==NULL&&p->rchild!=NULL){
            if(!f)
            T=p->rchild;
            else{
                if(mark==0)
                f->lchild=p->rchild;
                else
                f->rchild=p->rchild;
            }
            free(p);
            p=NULL;
            taller=TRUE;
        }
        else if(p->lchild==NULL&&p->rchild==NULL){
            if(!f)
            T=NULL;
            else{
                if(mark==0)
                f->lchild=NULL;
                else
                f->rchild=NULL;
            }
            free(p);
            p=NULL;
            taller=TRUE;
        }
        else{
            r=p->lchild;
            while(r->rchild)
            r=r->rchild;
            tmp=r->data;
            taller=FALSE;
            if(!f)
            DeleteAVL(T,tmp,NULL,p,taller,mark);
            else{
                if(mark==0)
                DeleteAVL(f->lchild,tmp,NULL,p,taller,mark);
                else
                DeleteAVL(f->rchild,tmp,NULL,p,taller,mark);
            }
            p->data=tmp;
        }
    }
    return OK;
}
}

int main(){
    BBSTree T1=NULL;
    int taller;
    int i,t;
    //T1=MakeBBSTree();
    int N[12]={88,29,91,19,50,32,24,45,62,79,52,67};
    int num=12;
    CreateAVL(&T1,N,num);
    PrintAVL(T1);
    while(1){
        printf("输入操作序号:1 查看T1,2 插入T1,3 删除T1,4 离开:\n");
        scanf("%d",&t);
        switch(t){
            case 1:PrintAVL(T1);break;
            case 2:
                printf("输入要插入的数字:\n");
                scanf("%d",&t);
                InsertAVL(&T1,t,taller);
                PrintAVL(T1);
                break;
            case 3:
                printf("输入要删除的数字:\n");
                scanf("%d",&t);
                DeleteAVL(T1,t,NULL,T1,taller,0);
                PrintAVL(T1);
                break;
            case 4:
                exit(0);
                default:
                    printf("非法输入!\n");
                    break;
        }
    }
}

太乱了,没时间改了,下班。
1