平衡二叉树[原创] - C++ - 新微赢技术网

泪在爱上雕刻

电梯直达

1^#

发表于 2009-11-3 01:59:26 | 只看该作者回帖奖励

|正序浏览 |阅读模式

这个东东就是要花一点时间画图研究。以下是我的代码。写得差请见谅 #include <status.h>
typedef struct BT{ int data; struct BT* l; struct BT* r; int bl; BT(int d); }BT;
BT::BT(int d){ l=r=NULL; data=d; bl=0; }
void clear(BT* p){ if(p){ clear(p->l); clear(p->r); delete(p); } }
void print(BT* p){ cout<<"data="<<p->data<<'\t'<<"bl="<<p->bl<<endl; }
void f_p(BT* T){ if(T!=NULL){ print(T); f_p(T->l); f_p(T->r); } }
void m_p(BT* T){ if(T!=NULL){ m_p(T->l); print(T); m_p(T->r); } }
void Trans(BT* T){ cout<<"\nfront trans:\n"; f_p(T); cout<<endl; cout<<"\nmid trans:\n"; m_p(T); cout<<endl; }
void Rotate_1(BT* &p){ BT* T=p->l; p->bl=0; T->bl=0; p->l=T->r; T->r=p; p=T; }
void Rotate_2(BT* &p){ BT* T=p->l->r; if(T->bl==0){ p->l->bl=p->bl=0; } else{ if(T->bl==1){ p->bl=-1; } else{ p->l->bl=1; } } p->l->r=T->l; T->l=p->l; p->l=T->r; T->r=p; p=T; }
void Rotate_3(BT* &p){ BT* T=p->r; p->bl=T->bl=0; p->r=T->l; T->l=p; p=T; }
void Rotate_4(BT* &p){ BT* T=p->r->l; if(T->bl==0){ p->r->bl=p->bl=0; } else{ if(T->bl==1){ p->r->bl=-1; } else{ p->bl=1; } } p->r->l=T->r; T->r=p->r; p->r=T->l; T->l=p; p=T; }
void Avl_Tree(BT* &p){ if(p->bl==2){ if(p->l->bl==1) Rotate_1(p); else Rotate_2(p); } else{ //p->bl==-2 if(p->r->bl==-1) Rotate_3(p); else Rotate_4(p); } }
status _Insert(int d,BT* &p,short int &f,short int &af){ if(!p){ p=new BT(d); f=SUCCESS; return TRUE; } else{ if(d>p->data){ if(_Insert(d,p->l,f,af)){ if(!p->r) af=TRUE; else{ af=FALSE; p->bl++; } } if(af==TRUE){ p->bl++; if(p->bl==2){ Avl_Tree(p); af=FALSE; } } } else if(d<p->data){ if(_Insert(d,p->r,f,af)){ if(!p->l) af=TRUE; else{ af=FALSE; p->bl--; } } if(af==TRUE){ p->bl--; if(p->bl==-2){ Avl_Tree(p); af=FALSE; } } } else{ f=FAILE; } return FALSE; } }
status Insert(int d,BT* &p){ short int f=SUCCESS; short int af=FALSE; _Insert(d,p,f,af); return f; }
void t1(){ BT* p=NULL; int d=1; cout<<"insert data="; cin>>d; while(d!=0){ if(Insert(d,p)) cout<<"\tInsert success"<<endl; else cout<<"\tInsert failed"<<endl; cout<<"insert data="; cin>>d; } Trans(p); getch(); clear(p); }
void main(){ t1(); }

收藏0