《平衡二叉树实现代码》由会员分享，可在线阅读，更多相关《平衡二叉树实现代码（5页珍藏版）》请在金锄头文库上搜索。
1、数据构造算法:平衡二叉树实现代码找了很久才找到的平衡二叉树实现代码#include typedef struct bitreetypeint item;int bdegree;/*平衡因子,左子树深度-右子树深度*/ struct bitreetype *lchild;struct bitreetype *rchild;bitree;typedef struct treequeuetypeint head; int tail;bitree *items1000;treequeue;/*定义一个队列,后面的平衡调整要用层序遍历,于是要用这个队列*/ void resetqueue(treeque
2、ue *queue)queue-head=-1; queue-tail=-1; return;/*把队列清空*/void inqueue(treequeue *queue,bitree *element)queue-tail+;queue-itemsqueue-tail=element;/*入队列*/bitree *outqueue(treequeue *queue)queue-head+;return queue-itemsqueue-head;/*出队列*/int isqueueempty(treequeue *queue)if(queue-head=queue-tail) return
3、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; in
4、t 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 临时空间中*/elsenum=p;*dst=atoi(num); len+; fillmemory(num,20,0); dst+;t=*temp
5、; 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(sourceitem)if(head-lchild=NULL)head-lchild=(bitre
6、e *)malloc(sizeof(bitree); head-lchild-item=source;head-lchild-lchild=NULL; head-lchild-rchild=NULL; head-lchild-bdegree=0;elseinsertbitree(head-lchild,source);elseif(head-rchild=NULL)head-rchild=(bitree *)malloc(sizeof(bitree); head-rchild-item=source;head-rchild-lchild=NULL; head-rchild-rchild=NUL
7、L; head-rchild-bdegree=0;elseinsertbitree(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-rc
8、hild=NULL; head-item=*source; head-bdegree=0; source+;len-; while(len0)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(he
9、ad-lchild);rtemp=1+getdepth(head-rchild); if(ltemp=rtemp)return ltemp; else return rtemp;/*递归求深的思想:首先规定好 0,1 两个递归出口,然后分别求左右子树的深度并返void addbdegree(bitree *head)/*为排序二叉树追加平衡因子*/if(head=NULL)return; elsehead-bdegree=getdepth(head-lchild)-getdepth(head-rchild); addbdegree(head-lchild);addbdegree(head-rc
10、hild);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-bdegreebdegree=2)if(temp-bdegree=2 && te
11、mp-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 &
12、;& 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);/*递归查找一个节点的妈妈*/
