要求有父亲结点平衡二叉树的建立
要能够形象方便地观察树的结构；要能够形象的演示树的平衡过程
#include<stdio.h>
#include<stdlib.h>
typedef struct BF
{
int data;
int parent;
int left;
int right;
int bf;
}BF;
typedef struct Bitree
{
int data;
struct Bitree *right;
struct Bitree *left;
struct Bitree *parent;
}Bitree;
typedef struct
{
Bitree *base;
int top;
int bottom;
int size;
}queue;
BF c[100];
void inistall(queue &q)
{
q.base=(Bitree *)malloc(sizeof(Bitree)*100);
q.top=q.bottom=0;
q.size=100;
}
void push(Bitree t,queue &q)
{
if(q.top==100)
printf("queue full\n");
q.base[q.top++]=t;
}
int empty(queue q)
{
if(q.top==q.bottom)
return 1;
else
return 0;
}
void pop(Bitree *&temp,queue &q)
{
if(q.top==q.bottom)
printf("queue null\n");
else
temp=&(q.base[q.bottom++]);
}
void travel(Bitree *t)
{
queue q;
Bitree *temp;
inistall(q);
push(*t,q);
while(!empty(q))
{
pop(temp,q);
printf("%d ",temp->data);
if(temp->left)
push(*temp->left,q);
if(temp->right)
push(*temp->right,q);
}
}
////////////////////////////
int Deep(Bitree *T)
{
int k,left,right;
if(!T)k=0;
else
{
right=Deep(T->right);
left=Deep(T->left);
if(right>left)k=1+right;
else k=1+left;
}
return k;
}
int locate(int n)
{
int i;
for(i=0;i<100;i++)
if(c[i].data==n)
return i;
}
void B1(Bitree *T)
{
Bitree *p,*q;
int n1,n2;
if(T)
{
p=T;
q=p->left;
n1=locate(p->data);
if(q!=NULL)
{n2=locate(q->data);
c[n1].left=n2;
c[n2].parent=n1;
}
else
{
c[n1].left=-1;
}
q=p->right;
n1=locate(p->data);
if(q!=NULL)
{n2=locate(q->data);
c[n1].right=n2;
c[n2].parent=n1;
}
else
{
c[n1].right=-1;
}
B1(T->left);
B1(T->right);
}
}
void B2(Bitree *T)
{
int n,left,right;
if(T)
{
left=Deep(T->left);
right=Deep(T->right);
n=locate(T->data);
c[n].bf=left-right;
B2(T->left);
B2(T->right);
}
}
void B(Bitree *T)
{
int i;
for(i=0;i<100;i++)
c[i].parent=c[i].left=c[i].right=-1;
B1(T);
B2(T);
}
void inistall(int a[],int n)
{
int i;
for(i=0;i<n;i++)
{
c[i].data=a[i];
c[i].left=c[i].right=c[i].parent=-1;
c[i].bf=0;
}
}
void find(Bitree *T,int data,Bitree *&p)
{
if(T)
{
if(T->data==data)
p=T;
find(T->left,data,p);
find(T->right,data,p);
}
}
int hunt(Bitree *p,Bitree *q)
{
if(p)
{
if(p->data==q->data)
return 1;
else
{
if(hunt(p->left,q))
return 1;
else
return hunt(p->right,q);
}
}
else return 0;
}
int kind(Bitree *p,Bitree *q)
{
Bitree *r,*s;
int k;
if(p->right!=NULL)
{
r=p->right;
s=r->right;
if((s!=NULL)&&(hunt(s,q)))
k=2;//RR
s=r->left;
if((s!=NULL)&&(hunt(s,q)))
k=3;//RL
}
if(p->left!=NULL)
{
r=p->left;
s=r->right;
if((s!=NULL)&&(hunt(s,q)))
k=4;//LR
s=r->left;
if((s!=NULL)&&(hunt(s,q)))
k=1;//LL
}
return k;
}
int pos(Bitree *r,Bitree *q)
{
int k;
if(r->left==q)k=2;
if(r->right==q)k=1;
return k;
}
void deal(Bitree *&T,int data)
{
int i,k=0,j,e;
Bitree *p,*q,*r,*temp;
i=locate(data);
while(c[i].bf<2&&c[i].bf>-2&&i!=-1)
i=c[i].parent;
if((c[i].bf>1||c[i].bf<-1)&&(i!=-1))
{
find(T,c[i].data,p);
j=c[i].parent;
find(T,data,q);
if(j!=-1)//r存在
{
find(T,c[j].data,r);
e=pos(r,p);//e:1为p是r的右孩子 2为p是r的左孩子
k=kind(p,q);//1:LL 2:RR 3:RL 4:LR
if(e==1)//p是r的右孩子
{
switch(k)
{
case 1:
p->left->parent=r;
p->parent=p->left;
if(p->left->right)
p->left->right->parent=p;
//////////
r->right=p->left;
p->left=r->right->right;
r->right->right=p;
break;
case 2:
p->right->parent=r;
p->parent=p->right;
if(p->right->left)
p->right->left->parent=p;
////////
r->right=p->right;
p->right=r->right->left;
r->right->left=p;
break;
case 3:
p->right->left->parent=r;
p->parent=p->right->left;
if(p->right->left->left)
p->right->left->left->parent=p;
if(p->right->left->right)
p->right->left->right->parent=p->right;
p->right->parent=p->right->left;
////////
temp=p->right->left;
p->right->left=temp->right;
temp->right=p->right;
p->right=temp;
p->right=temp->left;
temp->left=p;
r->right=temp;
break;
case 4:
p->left->right->parent=r;
p->left->parent=p->left->right;
p->parent=p->left->right;
if(p->left->right->left)
p->left->right->left->parent=p->left;
if(p->left->right->right)
p->left->right->right->parent=p;
//////////
temp=p->left->right;
p->left->right=temp->left;
temp->left=p->left;
p->left=temp;
p->left=temp->right;
temp->right=p;
r->right=temp;
break;
default:break;
}
}
if(e==2)//p是r的左孩子
{
switch(k)
{
case 1:
p->left->parent=r;
p->parent=p->left;
if(p->left->right)
p->left->right->parent=p;
//////////
r->left=p->left;
p->left=r->left->right;
r->left->right=p;
break;
case 2:
p->right->parent=r;
p->parent=p->right;
if(p->right->left)
p->right->left->parent=p;
////////
p->right=r->left->left;
r->left->left=p;
break;
case 3:
p->right->left->parent=r;
p->parent=p->right->left;
if(p->right->left->left)
p->right->left->left->parent=p;
if(p->right->left->right)
p->right->left->right->parent=p->right;
p->right->parent=p->right->left;
////////
temp=p->right->left;
p->right->left=temp->right;
temp->right=p->right;
p->right=temp;
p->right=temp->left;
temp->left=p;
r->left=temp;
break;
case 4:
p->left->right->parent=r;
p->left->parent=p->left->right;
p->parent=p->left->right;
if(p->left->right->left)
p->left->right->left->parent=p->left;
if(p->left->right->right)
p->left->right->right->parent=p;
//////////
temp=p->left->right;
p->left->right=temp->left;
temp->left=p->left;
p->left=temp;
p->left=temp->right;
temp->right=p;
r->left=temp;
break;
default:break;
}
}
B(T);
}
else//A为头结点
{
k=kind(p,q);//1:LL 2:RR 3:RL 4:LR
switch(k)
{
case 1:
T->left->parent=NULL;
T->parent=T->left;
if(T->left->right)
T->left->right->parent=T;
////////
T=p->left;
p->left=T->right;
T->right=p;
break;
case 2:
T->right->parent=NULL;
T->parent=T->right;
if(T->right->left)
T->right->left->parent=T;
/////////
T=p->right;
p->right=T->left;
T->left=p;
break;
case 3:
p->right->left->parent=NULL;
p->parent=p->right->left;
p->right->parent=p->right->left;
if(p->right->left->left)
p->right->left->left->parent=p;
if(p->right->left->right)
p->right->left->right->parent=p->right;
///////////
temp=p->right->left;
p->right->left=temp->right;
temp->right=p->right;
p->right=temp;
p->right=temp->left;
temp->left=p;
T=temp;
break;
case 4:p->left->right->parent=NULL;
p->left->parent=p->left->right;
p->parent=p->left->right;
if(p->left->right->left)
p->left->right->left->parent=p->left;
if(p->left->right->right)
p->left->right->right->parent=p;
///////////
temp=p->left->right;
p->left->right=temp->left;
temp->left=p->left;
p->left=temp;
p->left=temp->right;
temp->right=p;
T=temp;
break;
default:break;
}
B(T);
}
}
}
void creat(Bitree *&T)
{
int i,k,D[100],n,j;
Bitree *p,*q,*R,*S,*G;
printf("请输入数据个数\n");
scanf("%d",&n);
getchar();
for(i=0;i<n;i++)
{
printf("第%d个数据：\n",i+1);
scanf("%d",&D[i]);
}
inistall(D,n);
for(i=0;i<n;i++)
{
if(i==0)
{
p=q=T=(Bitree *)malloc(sizeof(Bitree));
p->data=D[i];
p->left=p->right=NULL;
T->parent=NULL;
B(T);
continue;
}
q=(Bitree *)malloc(sizeof(Bitree));
q->data=D[i];
q->left=q->right=NULL;
p=T;
while(p!=NULL)
{
G=p;
if(D[i]>p->data)
p=p->right;
else
p=p->left;
}
if(D[i]>G->data)
{
q->parent=G;
G->right=q;
}
else
{
q->parent=G;
G->left=q;
}
B(T);
deal(T,D[i]);
}//for
}
void main()
{
Bitree *T;
creat(T);
printf("生成的平衡二叉树为：\n");
travel(T);
}给你也发一下吧，，，同学弄的可是需要改一下