第1个回答 2008-07-01
平衡二叉树是:左右子树都是平衡二叉树,且左右子树的深度相差<=1
#include <stdio.h>
#include <stdlib.h>
typedef struct bitreetype
{
int item;
int bdegree;/*平衡因子,左子树深度-右子树深度*/
struct bitreetype *lchild;
struct bitreetype *rchild;
}bitree;
typedef struct treequeuetype
{
int head;
int tail;
bitree *items[1000];
}treequeue;/*定义一个队列,后面的平衡调整要用层序遍历,于是要用这个队列*/
void resetqueue(treequeue *queue)
{
queue->head=-1;
queue->tail=-1;
return;
}/*把队列清空*/
void inqueue(treequeue *queue,bitree *element)
{
queue->tail++;
queue->items[queue->tail]=element;
}/*入队列*/
bitree *outqueue(treequeue *queue)
{
queue->head++;
return queue->items[queue->head];
}/*出队列*/
int isqueueempty(treequeue *queue)
{
if(queue->head==queue->tail)
return 1;
else
return 0;
}/*判断队列是否为空*/
void fillmemory(char *source,int len,char content)
{
while(len)
{
source=source+len;
*source=content;
source=source-len;
len--;
}
*source=0;
}/*用CONTENT的内容去FILL以SOURCE为首,LEN长度的一块空间,初始化内存方便*/
int getnums(int *dst)/*输入字符串并把字符串转化为一串数存入DST指向的内存中去,我们用它采集原始数据*/
{
char *temp,*num,*p,t;
int len=0;
temp=(char *)malloc(1000*sizeof(char));
num=(char *)malloc(20*sizeof(char));
p=num;
fillmemory(temp,1000,0);
fillmemory(num,20,0);
scanf("%s",temp);
t=*temp;
temp++;
while(t)
{
if(t!=',')
{
*num=t;
num++;
t=*temp;
temp++;
}/*抽出一个数放入NUM临时空间中*/
else
{
num=p;
*dst=atoi(num);
len++;
fillmemory(num,20,0);
dst++;
t=*temp;
temp++;
}/*将NUM中的数字转化出来存入DST中*/
}
num=p;
*dst=atoi(num);
len++;
fillmemory(num,20,0);
dst++;
t=*temp;
temp++;
return len;
}/*处理最后一个数字*/
/*****唉,写上面的函数时都两个月没写过C了,所以可能上面的函数条理相当差的说*****/
void insertbitree(bitree *head,int source)/*向以HEAD为头结点的排序二叉树中插入一个以SOURCE为内容的点*/
{
if(source<=head->item)
{
if(head->lchild==NULL)
{
head->lchild=(bitree *)malloc(sizeof(bitree));
head->lchild->item=source;
head->lchild->lchild=NULL;
head->lchild->rchild=NULL;
head->lchild->bdegree=0;
}
else
insertbitree(head->lchild,source);
}
else
{
if(head->rchild==NULL)
{
head->rchild=(bitree *)malloc(sizeof(bitree));
head->rchild->item=source;
head->rchild->lchild=NULL;
head->rchild->rchild=NULL;
head->rchild->bdegree=0;
}
else
insertbitree(head->rchild,source);
}
}/*递归插入的思想:如果SOURCE小于头结点,那么插入头结点的左孩子,否则插入右孩子,递归向下,直到找到空位置为止*/
bitree *createbitree(int *source,int len)/*用SOURCE为首地址,LEN为长度的一段空间中的内容建立一棵二叉数*/
{
int temp;
bitree *head=NULL;
head=(bitree *)malloc(sizeof(bitree));
head->lchild=NULL;
head->rchild=NULL;
head->item=*source;
head->bdegree=0;
source++;
len--;
while(len>0)
{
insertbitree(head,*source);/*这个函数很强大,用心体会吧,哈哈哈*/
source++;
len--;
}
return head;
}
int getdepth(bitree *head)/*求排序二叉树的深度*/
{
int ltemp,rtemp;
if(head==NULL)return 0;
if(head->lchild==NULL && head->rchild==NULL)return 1;
ltemp=1+getdepth(head->lchild);
rtemp=1+getdepth(head->rchild);
if(ltemp>=rtemp)return ltemp;
else return rtemp;
}/*递归求深的思想:首先规定好0,1两个递归出口,然后分别求左右子树的深度并返回大者*/
void addbdegree(bitree *head)/*为排序二叉树追加平衡因子*/
{
if(head==NULL)return;
else
{
head->bdegree=getdepth(head->lchild)-getdepth(head->rchild);
addbdegree(head->lchild);
addbdegree(head->rchild);
}
}
bitree *leveldetect(bitree *head)/*以层序遍历为基本框架,检查"特殊"点*/
{
treequeue *tqueue;
bitree *temp;
tqueue=(treequeue *)malloc(sizeof(treequeue));
resetqueue(tqueue);
if(head!=NULL)inqueue(tqueue,head);
while(!isqueueempty(tqueue))
{
temp=outqueue(tqueue);
if(temp->bdegree<=-2 || temp->bdegree>=2)
{
if(temp->bdegree==2 && temp->lchild!=NULL && temp->lchild->bdegree==1)
return temp;
if(temp->bdegree==2 && temp->lchild!=NULL && temp->lchild->bdegree==-1)
return temp;
if(temp->bdegree==-2 && temp->rchild!=NULL && temp->rchild->bdegree==-1)
return temp;
if(temp->bdegree==-2 && temp->rchild!=NULL && temp->rchild->bdegree==1)
return temp;
}
if(temp->lchild!=NULL)inqueue(tqueue,temp->lchild);
if(temp->rchild!=NULL)inqueue(tqueue,temp->rchild);
}
return NULL;
}/*(2,1),(2,-1),(-2,-1),(-2,1)完美的卡诺图啊!!*/
bitree *getmother(bitree *head,bitree *child)
{
bitree *temp;
if(head==child)return NULL;
if(head->lchild==child || head->rchild==child)return head;
if(head->lchild==NULL || head->rchild==NULL)return NULL;
if(head->lchild!=NULL)
{
temp=getmother(head->lchild,child);
if(temp!=NULL)return temp;
}
return getmother(head->rchild,child);
}/*递归查找一个节点的妈妈*/
bitree *createsuperbitree(int *source,int len)/*不消说了,建立平衡二叉树*/
{
int itemp;
bitree *head=NULL;
bitree *temp=NULL;
bitree *tmother=NULL;
bitree *p=NULL;
bitree *q=NULL;
head=(bitree *)malloc(sizeof(bitree));
head->lchild=NULL;
head->rchild=NULL;
head->item=*source;
head->bdegree=0;
source++;
len--;
while(len>0)
{
insertbitree(head,*source);
addbdegree(head);
temp=leveldetect(head);
if(temp!=NULL)
{
tmother=getmother(head,temp);
if(temp->bdegree==2 && temp->lchild!=NULL && temp->lchild->bdegree==1)
{
p=temp->lchild;
temp->lchild=p->rchild;
p->rchild=temp;
if(tmother!=NULL)
{
if(tmother->lchild==temp)tmother->lchild=p;
else tmother->rchild=p;
}
else
head=p;
}/*LL*/
if(temp->bdegree==2 && temp->lchild!=NULL && temp->lchild->bdegree==-1)
{
p=temp->lchild->rchild;
q=temp->lchild;
q->rchild=p->lchild;
temp->lchild=p->rchild;
p->lchild=q;
p->rchild=temp;
if(tmother!=NULL)
{
if(tmother->lchild==temp)tmother->lchild=p;
else tmother->rchild=p;
}
else
head=p;
}/*LR*/
if(temp->bdegree==-2 && temp->rchild!=NULL && temp->rchild->bdegree==-1)
{
p=temp->rchild;
temp->rchild=p->lchild;
p->lchild=temp;
if(tmother!=NULL)
{
if(tmother->lchild==temp)tmother->lchild=p;
else tmother->rchild=p;
}
else
head=p;
}/*RR*/
if(temp->bdegree==-2 && temp->rchild!=NULL && temp->rchild->bdegree==1)
{
p=temp->rchild->lchild;
q=temp->rchild;
temp->rchild=p->lchild;
q->lchild=p->rchild;
p->lchild=temp;
p->rchild=q;
if(tmother!=NULL)
{
if(tmother->lchild==temp)tmother->lchild=p;
else tmother->rchild=p;
}
else
head=p;
}/*RL*/
addbdegree(head);
}
source++;
len--;
}
return head;
}
main()/*演示*/
{
int binums[100],i,len;
bitree *head,*temp;
for(i=0;i<=99;i++)binums[i]=0;
len=getnums(binums);
head=createsuperbitree(binums,len);
temp=getmother(head,head->rchild->rchild->rchild);
}
第2个回答 2008-07-01
找了很久才找到的平衡二叉树实现代码
#include <stdio.h>
typedef struct bitreetype
{
int item;
int bdegree;/*平衡因子,左子树深度-右子树深度*/
struct bitreetype *lchild;
struct bitreetype *rchild;
}bitree;
typedef struct treequeuetype
{
int head;
int tail;
bitree *items[1000];
}treequeue;/*定义一个队列,后面的平衡调整要用层序遍历,于是要用这个队列*/
void resetqueue(treequeue *queue)
{
queue->head=-1;
queue->tail=-1;
return;
}/*把队列清空*/
void inqueue(treequeue *queue,bitree *element)
{
queue->tail ;
queue->items[queue->tail]=element;
}/*入队列*/
bitree *outqueue(treequeue *queue)
{
queue->head ;
return queue->items[queue->head];
}/*出队列*/
int isqueueempty(treequeue *queue)
{
if(queue->head==queue->tail)
return 1;
else
return 0;
}/*判断队列是否为空*/
void fillmemory(char *source,int len,char content)
{
while(len)
{
source=source len;
*source=content;
source=source-len;
len--;
}
*source=0;
}/*用CONTENT的内容去FILL以SOURCE为首,LEN长度的一块空间,初始化内存方便*/
int getnums(int *dst)/*输入字符串并把字符串转化为一串数存入DST指向的内存中去,我们用它采集原始数据*/
{
char *temp,*num,*p,t;
int len=0;
temp=(char *)malloc(1000*sizeof(char));
num=(char *)malloc(20*sizeof(char));
p=num;
fillmemory(temp,1000,0);
fillmemory(num,20,0);
scanf("%s",temp);
t=*temp;
temp ;
while(t)
{
if(t!=',')
{
*num=t;
num ;
t=*temp;
temp ;
}/*抽出一个数放入NUM临时空间中*/
else
{
num=p;
*dst=atoi(num);
len ;
fillmemory(num,20,0);
dst ;
t=*temp;
temp ;
}/*将NUM中的数字转化出来存入DST中*/
}
num=p;
*dst=atoi(num);
len ;
fillmemory(num,20,0);
dst ;
t=*temp;
temp ;
return len;
}/*处理最后一个数字*/
/*****唉,写上面的函数时都两个月没写过C了,所以可能上面的函数条理相当差的说*****/
void insertbitree(bitree *head,int source)/*向以HEAD为头结点的排序二叉树中插入一个以SOURCE为内容的点*/
{
if(source<=head->item)
{
if(head->lchild==NULL)
{
head->lchild=(bitree *)malloc(sizeof(bitree));
head->lchild->item=source;
head->lchild->lchild=NULL;
head->lchild->rchild=NULL;
head->lchild->bdegree=0;
}
else
insertbitree(head->lchild,source);
}
else
{
if(head->rchild==NULL)
{
head->rchild=(bitree *)malloc(sizeof(bitree));
head->rchild->item=source;
head->rchild->lchild=NULL;
head->rchild->rchild=NULL;
head->rchild->bdegree=0;
}
else
insertbitree(head->rchild,source);
}
}/*递归插入的思想:如果SOURCE小于头结点,那么插入头结点的左孩子,否则插入右孩子,递归向下,直到找到空位置为止*/
bitree *createbitree(int *source,int len)/*用SOURCE为首地址,LEN为长度的一段空间中的内容建立一棵二叉数*/
{
int temp;
bitree *head=NULL;
head=(bitree *)malloc(sizeof(bitree));
head->lchild=NULL;
head->rchild=NULL;
head->item=*source;
head->bdegree=0;
source ;
len--;
while(len>0)
{
insertbitree(head,*source);/*这个函数很强大,用心体会吧,哈哈哈*/
source ;
len--;
}
return head;
}
int getdepth(bitree *head)/*求排序二叉树的深度*/
{
int ltemp,rtemp;
if(head==NULL)return 0;
if(head->lchild==NULL && head->rchild==NULL)return 1;
ltemp=1 getdepth(head->lchild);
rtemp=1 getdepth(head->rchild);
if(ltemp>=rtemp)return ltemp;
else return rtemp;
}/*递归求深的思想:首先规定好0,1两个递归出口,然后分别求左右子树的深度并返回大者*/
void addbdegree(bitree *head)/*为排序二叉树追加平衡因子*/
{
if(head==NULL)return;
else
{
head->bdegree=getdepth(head->lchild)-getdepth(head->rchild);
addbdegree(head->lchild);
addbdegree(head->rchild);
}
}
bitree *leveldetect(bitree *head)/*以层序遍历为基本框架,检查"特殊"点*/
{
treequeue *tqueue;
bitree *temp;
tqueue=(treequeue *)malloc(sizeof(treequeue));
resetqueue(tqueue);
if(head!=NULL)inqueue(tqueue,head);
while(!isqueueempty(tqueue))
{
temp=outqueue(tqueue);
if(temp->bdegree<=-2 || temp->bdegree>=2)
{
if(temp->bdegree==2 && temp->lchild!=NULL && temp->lchild->bdegree==1)
return temp;
if(temp->bdegree==2 && temp->lchild!=NULL && temp->lchild->bdegree==-1)
return temp;
if(temp->bdegree==-2 && temp->rchild!=NULL && temp->rchild->bdegree==-1)
return temp;
if(temp->bdegree==-2 && temp->rchild!=NULL && temp->rchild->bdegree==1)
return temp;
}
if(temp->lchild!=NULL)inqueue(tqueue,temp->lchild);
if(temp->rchild!=NULL)inqueue(tqueue,temp->rchild);
}
return NULL;
}/*(2,1),(2,-1),(-2,-1),(-2,1)完美的卡诺图啊!!*/
bitree *getmother(bitree *head,bitree *child)
{
bitree *temp;
if(head==child)return NULL;
if(head->lchild==child || head->rchild==child)return head;
if(head->lchild==NULL || head->rchild==NULL)return NULL;
if(head->lchild!=NULL)
{
temp=getmother(head->lchild,child);
if(temp!=NULL)return temp;
}
return getmother(head->rchild,child);
}/*递归查找一个节点的妈妈*/
bitree *createsuperbitree(int *source,int len)/*不消说了,建立平衡二叉树*/
{
int itemp;
bitree *head=NULL;
bitree *temp=NULL;
bitree *tmother=NULL;
bitree *p=NULL;
bitree *q=NULL;
head=(bitree *)malloc(sizeof(bitree));
head->lchild=NULL;
head->rchild=NULL;
head->item=*source;
head->bdegree=0;
source ;
len--;
while(len>0)
{
insertbitree(head,*source);
addbdegree(head);
temp=leveldetect(head);
if(temp!=NULL)
{
tmother=getmother(head,temp);
if(temp->bdegree==2 && temp->lchild!=NULL && temp->lchild->bdegree==1)
{
p=temp->lchild;
temp->lchild=p->rchild;
p->rchild=temp;
if(tmother!=NULL)
{
if(tmother->lchild==temp)tmother->lchild=p;
else tmother->rchild=p;
}
else
head=p;
}/*LL*/
if(temp->bdegree==2 && temp->lchild!=NULL && temp->lchild->bdegree==-1)
{
p=temp->lchild->rchild;
q=temp->lchild;
q->rchild=p->lchild;
temp->lchild=p->rchild;
p->lchild=q;
p->rchild=temp;
if(tmother!=NULL)
{
if(tmother->lchild==temp)tmother->lchild=p;
else tmother->rchild=p;
}
else
head=p;
}/*LR*/
if(temp->bdegree==-2 && temp->rchild!=NULL && temp->rchild->bdegree==-1)
{
p=temp->rchild;
temp->rchild=p->lchild;
p->lchild=temp;
if(tmother!=NULL)
{
if(tmother->lchild==temp)tmother->lchild=p;
else tmother->rchild=p;
}
else
head=p;
}/*RR*/
if(temp->bdegree==-2 && temp->rchild!=NULL && temp->rchild->bdegree==1)
{
p=temp->rchild->lchild;
q=temp->rchild;
temp->rchild=p->lchild;
q->lchild=p->rchild;
p->lchild=temp;
p->rchild=q;
if(tmother!=NULL)
{
if(tmother->lchild==temp)tmother->lchild=p;
else tmother->rchild=p;
}
else
head=p;
}/*RL*/
addbdegree(head);
}
source ;
len--;
}
return head;
}
main()/*演示*/
{
int binums[100],i,len;
bitree *head,*temp;
for(i=0;i<=99;i )binums[i]=0;
len=getnums(binums);
head=createsuperbitree(binums,len);
temp=getmother(head,head->rchild->rchild->rchild);
}
第二个:
#define LH 1 /* 左高 */
#define EH 0 /* 等しい */
#define RH -1 /* 右高 */
#define True 1
#define False 0
#define Boolean int
#define RET_FOUND 0
#define RET_NOFOUND 1
typedef struct user_list_
{
char mail_address[512 +1]; /* 送信者address */
char mail_domain[255 +1]; /*domain*/
int count1; /* 送信件数, doman别送信通数, NDR送信通数 */
int count2; /* 送信通数 */
int bf; /* 平衡因子 */
struct user_list_ * ptnLeft; /* 左指针 */
struct user_list_ * ptnRight; /* 右指针 */
}USER_LIST;
typedef USER_LIST * PUSER_LIST;
/* 全局変数 */
Boolean taller;
/*平衡二叉树调整操作*/
void R_Rotate(PUSER_LIST *p)
{
/*对以*p指向的结点为根的子树,作右单旋转处理,处理之后,*p指向的结点为子树的新根*/
PUSER_LIST lp;
lp=(*p)->ptnLeft; /*lp指向*p左子树根结点*/
(*p)->ptnLeft=lp->ptnRight; /*lp的右子树挂接*p的左子树*/
lp->ptnRight=*p;
*p=lp; /* *p指向新的根结点*/
}
void L_Rotate(PUSER_LIST *p)
{
/*对以*p指向的结点为根的子树,作左单旋转处理,处理之后,*p指向的结点为子树的新根*/
PUSER_LIST lp;
lp=(*p)->ptnRight; /*lp指向*p右子树根结点*/
(*p)->ptnRight=lp->ptnLeft; /*lp的左子树挂接*p的右子树*/
lp->ptnLeft=*p;
*p=lp; /* *p指向新的根结点*/
}
void LeftBalance(PUSER_LIST *p)
{
/*对以*p指向的结点为根的子树,作左平衡旋转处理,处理之后,*p指向的结点为子树的新根*/
PUSER_LIST lp, rc;
lp=(*p)->ptnLeft; /*lp指向*p左子树根结点*/
[color=Red][size=4][b]switch((*p)->bf) /*检查*p平衡度,并作相应处理 ??(是否应该是检查lp的平衡度 )*/[/b][/size][/color]
{
case LH: /*新结点插在*p左子女的左子树上,需作单右旋转处理*/
(*p)->bf=lp->bf=EH;
R_Rotate(p);
break;
case EH: /*原本左、右子树等高,因左子树增高使树增高*/
(*p)->bf=LH;
break;
case RH: /*新结点插在*p左子女的右子树上,需作先左后右双旋处理*/
rc=lp->ptnRight; /*ptnRight指向*p左子女的右子树根结点*/
switch(rc->bf) /*修正*p及其左子女的平衡因子*/
{
case LH:
(*p)->bf=RH;
lp->bf=EH;
break;
case EH:
(*p)->bf=lp->bf=EH;
break;
case RH:
(*p)->bf=EH;
lp->bf=LH;
break;
}/*switch(ptnRight->bf)*/
rc->bf=EH;
L_Rotate(&((*p)->ptnLeft)); /*对*p的左子树作左旋转处理*/
R_Rotate(p); /*对*t作右旋转处理*/
}/*switch((*p)->bf)*/
}/*LeftBalance*/
void RightBalance(PUSER_LIST *p)
{
/*对以*p指向的结点为根的子树,作左平衡旋转处理,处理之后,*p指向的结点为子树的新根*/
PUSER_LIST lp, lc;
lp=(*p)->ptnRight; /*lp指向*p右子树根结点*/
switch((*p)->bf) /*检查*p平衡度,并作相应处理*/
{
case RH: /*新结点插在*p左子女的右子树上,需作单左旋转处理*/
(*p)->bf=lp->bf=EH;
L_Rotate(p);
break;
case EH: /*原本左、右子树等高,因左子树增高使树增高*/
(*p)->bf=RH;
break;
case LH: /*新结点插在*p左子女的左子树上,需作先右后左双旋处理*/
lc=lp->ptnLeft; /*ptnLeft指向*p右子女的左子树根结点*/
switch(lc->bf) /*修正*p及其右子女的平衡因子*/
{
case RH:
(*p)->bf=LH;
lp->bf=EH;
break;
case EH:
(*p)->bf=lp->bf=EH;
break;
case LH:
(*p)->bf=EH;
lp->bf=RH;
break;
}/*switch(ptnLeft->bf)*/
lc->bf=EH;
R_Rotate(&((*p)->ptnLeft)); /*对*p的右子树作右旋转处理*/
L_Rotate(p); /*对*t作左旋转处理*/
}/*switch((*p)->bf)*/
}/*RightBalance*/
int insertNewAddress( PUSER_LIST * pptnHead, char *mailAddr, int cnt1, int cnt2, int cnt3, int errcnt Boolean *taller)
{
PUSER_LIST ptnCurr;
ptnCurr = *pptnHead;
if(ptnCurr == NULL)
{
ptnCurr = (PUSER_LIST)malloc(sizeof(USER_LIST));
ptnCurr->ptnLeft = NULL;
ptnCurr->ptnRight = NULL;
strcpy(ptnCurr->mail_address, mailAddr);
ptnCurr->count1 = cnt1;
ptnCurr->count2 = cnt2;
ptnCurr->count3 = cnt3;
ptnCurr->errcnt = errcnt;
*taller = True;
ptnCurr->bf = EH;
*pptnHead = ptnCurr;
}
else if(strcmp(oneUser->fee_number, ptnCurr->fee_number) < 0)
{
insertNewAddress(&(ptnCurr->ptnLeft), mailAddr, cnt1, cnt2, cnt3, errcnt, taller);
if(*taller) /*已插入到(*t)的左子树中,且左子树增高*/
{
switch(ptnCurr->bf) /*检查*t平衡度*/
{
case LH: /*原本左子树高,需作左平衡处理*/
LeftBalance(pptnHead); *taller=False;break;
case EH: /*原本左、右子树等高,因左子树增高使树增高*/
ptnCurr->bf=LH; *taller=True;break;
case RH: /*原本右子树高,使左、右子树等高*/
ptnCurr->bf=EH; *taller=False;break;
}
}
}
else
{
insertNewAddress(&(ptnCurr->ptnRight), mailAddr, cnt1, cnt2, cnt3, errcnt, taller);
if(*taller) /*已插入到(*t)的左子树中,且左子树增高*/
{
switch(ptnCurr->bf) /*检查*t平衡度*/
{
case LH: /*原本左子树高,使左、右子树等高*/
ptnCurr->bf=EH; *taller=False;break;
case EH: /*原本左、右子树等高,因右子树增高使树增高*/
ptnCurr->bf=RH; *taller=True;break;
case RH: /*原本右子树高,需作右平衡处理*/
RightBalance(pptnHead); *taller=False;break;
}
}
}
return 0;
}
int searchAndAdd( PUSER_LIST *pptnHead, char *mailAddr, int cnt1, int cnt2, int cnt3, int errcnt)
{
PUSER_LIST ptnCurr;
ptnCurr = *pptnHead;
if (NULL == pptnHead)
{
return RET_NOFOUND;
}
while(ptnCurr != NULL)
{
if(strcmp(ptnCurr->mail_address, mailAddr) == 0)
{
ptnCurr->count1 += cnt1;
ptnCurr->count2 += cnt2;
ptnCurr->count3 += cnt3;
ptnCurr->errcnt += errcnt;
return RET_NOFOUND;
}
else if(strcmp(ptnCurr->mail_address, mailAddr) > 0)
{
ptnCurr = ptnCurr->ptnLeft;
}
else
{
ptnCurr = ptnCurr->ptnRight;
}
}
return RET_NOFOUND;
}