#include <stdio.h>
typedef struct bitreetype
{
int item;
int bdegree;/*平衡因子,左子樹(shù)深度-右子樹(shù)深度*/
struct bitreetype *lchild;
struct bitreetype *rchild;
}bitree;
typedef struct treequeuetype
{
int head;
int tail;
bitree *items[1000];
}treequeue;/*定義一個(gè)隊列,后面的平衡調整要用層序遍歷,于是要用這個(gè)隊列*/
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長(cháng)度的一塊空間,初始化內存方便*/
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++;
}/*抽出一個(gè)數放入NUM臨時(shí)空間中*/
else
{
num=p;
*dst=atoi(num);
len++;
fillmemory(num,20,0);
dst++;
t=*temp;
temp++;
}/*將NUM中的數字轉化出來(lái)存入DST中*/
}
num=p;
*dst=atoi(num);
len++;
fillmemory(num,20,0);
dst++;
t=*temp;
temp++;
return len;
}/*處理最后一個(gè)數字*/
/*****唉,寫(xiě)上面的函數時(shí)都兩個(gè)月沒(méi)寫(xiě)過(guò)C了,所以可能上面的函數條理相當差的說(shuō)*****/
void insertbitree(bitree *head,int source)/*向以HEAD為頭結點(diǎn)的排序二叉樹(shù)中插入一個(gè)以SOURCE為內容的點(diǎn)*/
{
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小于頭結點(diǎn),那么插入頭結點(diǎn)的左孩子,否則插入右孩子,遞歸向下,直到找到空位置為止*/
bitree *createbitree(int *source,int len)/*用SOURCE為首地址,LEN為長(cháng)度的一段空間中的內容建立一棵二叉數*/
{
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);/*這個(gè)函數很強大,用心體會(huì )吧,哈哈哈*/
source++;
len--;
}
return head;
}
int getdepth(bitree *head)/*求排序二叉樹(shù)的深度*/
{
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兩個(gè)遞歸出口,然后分別求左右子樹(shù)的深度并返回大者*/
void addbdegree(bitree *head)/*為排序二叉樹(shù)追加平衡因子*/
{
if(head==NULL)return;
else
{
head->bdegree=getdepth(head->lchild)-getdepth(head->rchild);
addbdegree(head->lchild);
addbdegree(head->rchild);
}
}
bitree *leveldetect(bitree *head)/*以層序遍歷為基本框架,檢查"特殊"點(diǎn)*/
{
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);
}/*遞歸查找一個(gè)節點(diǎn)的媽媽*/
bitree *createsuperbitree(int *source,int len)/*不消說(shuō)了,建立平衡二叉樹(shù)*/
{
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);
}
聯(lián)系客服
