二叉树

haoningabc

转http://www.cnblogs.com/fornever/archive/2011/11/15/2249492.html
一句话，出来混，早晚是要还的，天天弄java，mlgbd基础全忘光了
#include <stdio.h>#include <stdlib.h>#include <string.h>typedef int Elemtype;typedef struct Balanced_Binary_Tree{    Elemtype e;    int bf;    struct Balanced_Binary_Tree *child[2];}*AVL;///------------简单的位操作-------------------void setbit(char *i,char val,char pos){    if(pos==1)        (*i)=(*i)|1;    else    {        if(val==1)    (*i)=(*i)|2;        else    (*i)=(*i)&1;    }}char getbit(char i,char pos){    ///调试时，发现这里能返回2/////    return (i&pos); 出错的地方    return (i&pos)&&1;    /////////////////////////////}///--------------------------------------------///-----------生成一个结点---------------------AVL createnode(Elemtype e){    AVL node=NULL;    node=(AVL)malloc(sizeof(struct Balanced_Binary_Tree));    node->e=e;    node->bf=0;    node->child[0]=node->child[1]=NULL;        return node;}///---------------------------------------------///★★★★★★★★AVL的核心操作★★★★★★★★★★★★///★★★★★★★★★保持平衡★★★★★★★★★★★★★★//改变因子函数void setfactor(AVL f,int button){    char fir=button/10,sec=button%10;    AVL s=f->child[fir],ss=s->child[sec];    char choice=ss->bf;    int a=1,b=0;    //////////调试时发现，删除时的特殊情况//////////////////插入时，不会有这种情况，若button=0,则s->bf=1///////若button=11，则s->bf=-1；然而删除时，却会出现//////button=0或者button=11时 s->bf=0!!!!!!!/////////////那么这种特殊情况，平衡后所得的因子就跟一般的///////不一样了!!!如下///////////////////////////////    if(button==0 && s->bf==0)    f->bf=1,s->bf=-1;    else if(button==11 && s->bf==0)    f->bf=-1,s->bf=1;    ///////////////////////////////////////////////////    else if(button==0 || button==11)    {        f->bf=0;        s->bf=0;    }    else    {        /////写博客时，发现这里有问题///////////////////    //    if(button==1)    choice=-choice;        /////但是为什么我测试的时候怎么都对?!////////////////经再次测试，上边确实错了!!!/////////////////////改为下边应该就对了吧///////////////////////        if(button==1)    {a^=b,b^=a,a^=b;}        ////////////////////////////////////////////////        if(choice==-1)    f->bf=a,s->bf=b;        else if(choice==0)    f->bf=s->bf=0;        else    f->bf=-b,s->bf=-a;                ss->bf=0;    }}//两节点变换函数void conversion(AVL *T,char direction){    AVL f=*T,s=f->child[direction];    f->child[direction]=s->child[!direction];    s->child[!direction]=f;    *T=s;}//保持平衡函数void keepbalance(AVL *T,char fir,char sec){    AVL *s=&((*T)->child[fir]);    int button=fir*10+sec;    if(button==0 || button==11)    {        setfactor((*T),button);        conversion(T,fir);    }    else    {        setfactor((*T),button);        conversion(s,sec);        conversion(T,fir);    }}///★★★★★★★★★★★★★★★★★★★★★★★★★★///------------插入时的选向操作-------------------void selectforInsert(AVL *T,char *info,int direction){    AVL cur=*T;    char firdirection,secdirection;    if(direction==0)    (cur->bf)++;    else    (cur->bf)--;    if(cur->bf==0)    setbit(info,1,1);    else if(cur->bf==-1 || cur->bf==1)    setbit(info,direction,2);    else    {                firdirection=direction;        secdirection=getbit(*info,2);        keepbalance(T,firdirection,secdirection);        setbit(info,1,1);    }}//----------------------------------------------//*************插入操作************************//char InsertAVL(AVL *T,Elemtype e){                                //可用于查询    char info;        if(!(*T))    {        (*T)=createnode(e);        return 0;    }    else if((*T)->e==e)        return -1;    else if((*T)->e>e)//左    {        info=InsertAVL(&((*T)->child[0]),e);        if(getbit(info,1))    return info;                selectforInsert(T,&info,0);    }    else              //右    {        info=InsertAVL(&((*T)->child[1]),e);        if(getbit(info,1))    return info;        selectforInsert(T,&info,1);    }    return info;}//*********************************************////-------------删除时的选向操作--------------------void selectforDelete(AVL *T,char *info,char direction){    AVL cur=(*T);    char firdirection,secdirection;    if(direction==0)    (cur->bf)--;    else    (cur->bf)++;        if(cur->bf==0)    *info=0;    else if(cur->bf==-1 || cur->bf==1)    *info=1;    else    {        firdirection=!direction;        ///调试时，发现这里少写了一个等号//////////////////////        if(cur->child[firdirection]->bf=1)    secdirection=0;草，真帅气!原来1==a这样写确实有必要!        if(1==cur->child[firdirection]->bf)    secdirection=0;        /////////////////////////////////////////////////////        else    secdirection=1;        keepbalance(T,firdirection,secdirection);        ////////////////////////////////////////////////////////////////////////////////////////////调试时，发现经过子树平衡操作后，*info不一定都是0，就是那个特殊情况，在setfactor中////////的那种特殊情况时，这里*info应改为1! 所以代码改如下：///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////    //    *info=1; 写代码时：这跟插入可不一样啊...该子树平衡了，它父节点的因子比变!//    *info=0;//因此，这还没完还要是0!! ............啊……这里不一定是0! ////还是那个特殊情况搞的鬼!//        if(cur->bf==0)    *info=0;        else    *info=1;        /////////////////////////////////////////////////////////////////////////////////////////    }}//------------------------------------------------//-------------变向递归--辅助删点-----------------char find(AVL *gogal,AVL *p){    char info;    AVL tp=NULL;        if(NULL!=(*p)->child[0])    {        info=find(gogal,&((*p)->child[0]));        if(info!=0)    return info;        selectforDelete(p,&info,0);    }    else    {        (*gogal)->e=(*p)->e;        tp=(*p)->child[1];        free((*p));        *p=tp;        info=0;    }    return info;}//------------------------------------------------//**************删除操作*************************//char DeleteAVL(AVL *T,Elemtype e){    char info;    AVL tp=NULL;    if(!(*T))    return -1;//原if(!T)    return -1;于2011年11月29日8:59:15修改    else if((*T)->e==e)    {        if(NULL!=(*T)->child[1])        {            info=find(T,&((*T)->child[1]));            if(info!=0)    return info;            selectforDelete(T,&info,1);        }        else        {            //////////////调试时，发现这样写不对!!!///////////////////////////////////////        //    (*T)=(p=(*T)->child[0])-(free((*T)),0);//Just save a variable! 这里出问题//    (*T)=p-(free((*T)),0); 可以//    (*T)=(p=((*T)->child[0]))+(free((*T)),0); 不可以            tp=((*T)->child[0]);            free((*T));            *T=tp;            //调试时，发现这里漏了给info赋值            info=0;            ///////////////////////////////////////////////////////////////////////////////        }    }    else if((*T)->e>e)    {        info=DeleteAVL(&(*T)->child[0],e);        if(info!=0)    return info;        selectforDelete(T,&info,0);    }    else    {        info=DeleteAVL(&(*T)->child[1],e);        if(info!=0)    return info;        selectforDelete(T,&info,1);    }    return info;}//************************************************////*****************JUST FOR TEST************************//#define MOVE(x)    (x=(x+1)%1000)AVL queue[1000];void print(AVL p,int i){    int front,rear,temp,count;    front=rear=-1; count=temp=0;    queue[MOVE(rear)]=p; count++;        printf("%d\n",i);    while(front!=rear)    {        p=queue[MOVE(front)];    count--;                        if(p->child[0])    queue[MOVE(rear)]=p->child[0],temp++;        if(p->child[1])    queue[MOVE(rear)]=p->child[1],temp++;                printf("%d->%d ",p->e,p->bf);        if(count==0)        {            printf("\n");            count=temp;            temp=0;        }        }    printf("\n");}//**************************************************//int main(){    AVL T=NULL;    int i,nodenum=0;    freopen("input.txt","w",stdout);    nodenum=100;    for(i=0;i<nodenum;i++)    {        InsertAVL(&T,i);    }        print(T,-1);    for(i=0;i<nodenum-1;i++)    {        DeleteAVL(&T,i);        print(T,i);    }        return 0;}