|
#2
杨焕发2011-01-07 10:27
#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); }给你也发一下吧，，，同学弄的可是需要改一下 |
要能够形象方便地观察树的结构；要能够形象的演示树的平衡过程