平衡二叉树源码 -- RocketMan'sRoom-- 编程爱好者博客

#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); }

博客介绍

正文

平衡二叉树源码2007-10-11 21:59:00

评论