📄 bnode.cpp
字号:
#include "BNode.h"
bool BOperation::Avltfind(BTreeText&atext){
BNode *p,*q;
q=atext.getRoot();
p=0;
while(q&&(q->key!=atext.the_key)){
p=q;
if(q->key>atext.the_key)q=q->llink.get();
else q=q->rlink.get();
}
if(q==0)return false;
else{
atext.the_node=q;
return true;
}
}
void BOperation::in_show(BNode*q,std::ostream&o,std::string road){
std::string s;
if(q->llink.get()!=0){in_show(q->llink.get(),o,road+"<");}
if(q->bf==0)s="(=)\t";
else if(q->bf<0)s="(-)\t";
else s="(+)\t";
q->show(s+road,o);
if(q->rlink.get()!=0){in_show(q->rlink.get(),o,road+">");}
}
void BOperation::Avltshow(BTreeText&atext,std::ostream&o){
BNode*q;
q=atext.getRoot();
if(q==0){
o<<"*Null Tree*"<<"\n";
return;
}
std::string road="";
in_show(q,o,road);
}
bool OperationA::Avltin(BTreeText&atext){
BNode*p,*q;
auto_ptr<BNode> newb;
q=atext.getRoot();
p=0;
while(q&&(q->key!=atext.the_key)){
p=q;
if(q->key>atext.the_key)q=q->llink.get();
else q=q->rlink.get();
}
if(q==0){
if(atext.photo==0)newb.reset(new BNode);
else newb=atext.photo->clone();
q=newb.get();
q->key=atext.the_key;
if(p==0)atext.tree_root=newb;
else if(atext.the_key<p->key)p->llink=newb;
else p->rlink=newb;
return true;
}else return false;
}
bool OperationA::AvltOut(BTreeText&atext){
BNode*p,*q,*r;
auto_ptr<BNode>s;
p=0;
q=atext.getRoot();
while(q&&(atext.the_key!=q->key)){
p=q;
if(atext.the_key<q->key)q=q->llink.get();
else q=q->rlink.get();
}
if(q==0)return false;
if(q->llink.get()==0)s=q->rlink;
else{
s=q->llink;
r=s.get();
while(r->rlink.get())
r=r->rlink.get();
r->rlink=q->rlink;
}
if(p==0)atext.tree_root=s;
else if(q==p->llink.get())p->llink=s;
else p->rlink=s;
return true;
}
void OperationB::LL(auto_ptr<BNode>&p,auto_ptr<BNode>&s,auto_ptr<BNode>&r){
s->bf+=r->bf;
r->bf+=1;
p=r;
r=p->rlink;
p->rlink=s;
s=p;
}
void OperationB::RR(auto_ptr<BNode>&p,auto_ptr<BNode>&s,auto_ptr<BNode>&r){
s->bf-=r->bf;
r->bf-=1;
p=r;
r=p->llink;
p->llink=s;
s=p;
}
void OperationB::LR(auto_ptr<BNode>&p,auto_ptr<BNode>&s,auto_ptr<BNode>&r){
auto_ptr<BNode> pp;
pp=p;
p=pp->llink;
pp->llink=r;
r=pp->rlink;
pp->rlink=s;
switch(pp->bf){
case -1:pp->llink->bf= 0;pp->rlink->bf=1;pp->bf=0;break;
case +1:pp->llink->bf=-1;pp->rlink->bf=0;pp->bf=0;break;
case 0:pp->llink->bf= 0;pp->rlink->bf=0;break;
}
s=pp;
}
void OperationB::RL(auto_ptr<BNode>&p,auto_ptr<BNode>&s,auto_ptr<BNode>&r){
auto_ptr<BNode> pp;
pp=p;
p=pp->rlink;
pp->rlink=r;
s->rlink=pp->llink;
pp->llink=s;
switch(pp->bf){
case -1:(pp->rlink)->bf=1;(pp->llink)->bf= 0;pp->bf=0;break;
case +1:(pp->rlink)->bf=0;(pp->llink)->bf=-1;pp->bf=0;break;
case 0:(pp->rlink)->bf=0;(pp->llink)->bf= 0;break;
}
s=pp;
}
bool OperationB::Avltin(BTreeText&atext){
BNode*s,*t,*p,*q,*r;
auto_ptr<BNode> as,aq;
s=atext.getRoot();
if(s==0){
if(atext.photo==0)as.reset(new BNode);
else as=atext.photo->clone();
as->bf=0;
as->key=atext.the_key;
atext.tree_root=as;
return true;
}
t=0;
p=0;
q=s;
while((q!=0)&&(q->key!=atext.the_key)){
if(q->bf){
t=p;s=q;
}
p=q;
if(atext.the_key<q->key)q=q->llink.get();
else q=q->rlink.get();
}
if(q!=0)return false;
if(atext.photo==0)aq.reset(new BNode);
else aq=atext.photo->clone();
q=aq.get();
q->key=atext.the_key;
q->bf=0;
if(atext.the_key<p->key)p->llink=aq;
else p->rlink=aq;
if(atext.the_key<s->key)r=s->llink.get();
else r=s->rlink.get();
p=r;
while(p!=q)if(atext.the_key<p->key){
p->bf=-1;
p=p->llink.get();
}else{
p->bf=1;
p=p->rlink.get();
}
switch(s->bf){
case 0:
if(atext.the_key<s->key)s->bf=-1;
else s->bf=1;
break;
case -1:
if(atext.the_key>s->key){
s->bf=0;
}else if(r->bf<0){
if(t==0)LL(as,atext.tree_root,s->llink);
else if(s->key<t->key)LL(as,t->llink,s->llink);
else LL(as,t->rlink,s->llink);
}else{
if(t==0)LR(r->rlink,atext.tree_root,s->llink);
else if(s->key<t->key)LR(r->rlink,t->llink,s->llink);
else LR(r->rlink,t->rlink,s->llink);
}
break;
case 1:
if(atext.the_key<s->key){
s->bf=0;
}else if(r->bf>0){
if(t==0){
RR(as,atext.tree_root,s->rlink);
}else if(s->key<t->key){
RR(as,t->llink,s->rlink);
}else RR(as,t->rlink,s->rlink);
}else{
if(t==0){
RL(r->llink,atext.tree_root,s->rlink);
}else if(s->key<t->key){
RL(r->llink,t->llink,s->rlink);
}else RL(r->llink,t->rlink,s->rlink);
}
break;
}
return true;
}
bool OperationB::AvltOut(BTreeText&atext){
auto_ptr<BNode> as;
bool inf=false;
BNode *p,*q,*r,*s,*t;
auto_ptr<stack> Stack,st;
s=atext.getRoot();
if(s==0)return false;
p=0;
q=s;
while(q&&(atext.the_key!=q->key)){
p=q;
st.reset(new stack);
st->x=q;
st->next=Stack;
Stack=st;
if(atext.the_key<q->key)q=q->llink.get();
else q=q->rlink.get();
}
if(q==0){
return false;
}
if((q->llink.get())&&(q->rlink.get())){
t=q;
p=q;
st.reset(new stack);
st->x=q;
st->next=Stack;
Stack=st;
if(q->bf<=0){
q=q->llink.get();
while(q){
p=q;
st.reset(new stack);
st->x=q;
st->next=Stack;
Stack=st;
q=q->rlink.get();
}
}else{
q=q->rlink.get();
while(q){
p=q;
st.reset(new stack);
st->x=q;
st->next=Stack;
Stack=st;
q=q->llink.get();
}
}
t->key=p->key;
atext.the_key=p->key;
q=p;
st=Stack;
Stack=Stack->next;
p=Stack->x;
}
if((q->llink.get()==0)&&(q->rlink.get()==0)){
if(p==0){
atext.tree_root.reset();
}else if(atext.the_key<p->key){
p->llink.reset();
}else if(atext.the_key==p->key){
if(p->bf<=0)p->llink.reset();
else p->rlink.reset();
}else{
p->rlink.reset();
}
}else if(q->llink.get()){
as=q->llink;
if(p==0){
atext.tree_root=as;
}else if(atext.the_key<p->key){
p->llink=as;
}else if(atext.the_key==p->key){
if(p->bf<=0)p->llink=as;
else p->rlink=as;
}else{
p->rlink=as;
}
}else{
as=q->rlink;
if(p==0){
atext.tree_root=as;
}else if(atext.the_key<p->key){
p->llink=as;
}else if(atext.the_key==p->key){
if(p->bf<=0)p->llink=as;
else p->rlink=as;
}else{
p->rlink=as;
}
}
inf=true;
while(Stack.get()&&(inf)){
s=Stack->x;
st=Stack;
Stack=Stack->next;
st.reset();
t=(Stack.get())?(Stack->x):(0);
if((atext.the_key<s->key)||(atext.the_key==s->key)&&(s->bf<=0))
switch(s->bf){
case 0:s->bf=1;inf=false;break;
case -1:s->bf=0;break;
case +1:
r=s->rlink.get();
if(r->bf>=0){
if(r->bf==0)inf=false;
if(t==0){
RR(as,atext.tree_root,s->rlink);
}else if(s->key<t->key){
RR(as,t->llink,s->rlink);
}else RR(as,t->rlink,s->rlink);
}else if(r->bf==-1){
if(t==0){
RL(r->llink,atext.tree_root,s->rlink);
}else if(s->key<t->key){
RL(r->llink,t->llink,s->rlink);
}else RL(r->llink,t->rlink,s->rlink);
}
break;
}else switch(s->bf){
case 0:s->bf=-1;inf=false;break;
case +1:s->bf=0;break;
case -1:
r=s->llink.get();
if(r->bf<=0){
if(r->bf==0)inf=false;
if(t==0)LL(as,atext.tree_root,s->llink);
else if(s->key<t->key)LL(as,t->llink,s->llink);
else LL(as,t->rlink,s->llink);
}else{
if(t==0)LR(r->rlink,atext.tree_root,s->llink);
else if(s->key<t->key)LR(r->rlink,t->llink,s->llink);
else LR(r->rlink,t->rlink,s->llink);
}
break;
}
}
return true;
}
bool OperationC::Avltin(BTreeText&atext){
CNode* ctp=(CNode*)atext.getphoto();
int num=ctp->count;
if(num<=0)return false;
auto_ptr<BOperation> bop;
bop.reset((_type==opa)?((BOperation*)new OperationA):((BOperation*)new OperationB));
bool result;
result=bop->Avltfind(atext);
ctp->count=num;
if(result){
((CNode*)(atext.the_node))->count+=num;
}else{
bop->Avltin(atext);
}
return true;
}
bool OperationC::AvltOut(BTreeText&atext){
CNode* ctp=(CNode*)atext.getphoto();
int num=ctp->count;
if(num<=0)return false;
auto_ptr<BOperation> bop;
bop.reset((_type==opa)?((BOperation*)new OperationA):((BOperation*)new OperationB));
bool result;
result=bop->Avltfind(atext);
ctp->count=num;
if(result){
CNode* cn=(CNode*)atext.the_node;
if(cn->count<=num){
bop->AvltOut(atext);
}else{
cn->count-=num;
}
}else{
return false;
}
return true;
}
auto_ptr<BNode> BNode::cloneAll(){
auto_ptr<BNode> b(new BNode);
b->key=this->key;
if(llink.get()!=0)b->llink=llink->cloneAll();
if(rlink.get()!=0)b->rlink=rlink->cloneAll();
return b;
}
auto_ptr<BNode> UNode::clone(){
auto_ptr<BNode> bu((BNode*)new UNode);
((UNode*)bu.get())->data=this->data;
return bu;
}
auto_ptr<BNode> UNode::cloneAll(){
UNode* pbu;
auto_ptr<BNode> bu((BNode*)(pbu=new UNode));
pbu->key=this->key;
pbu->data=this->data;
if(llink.get()!=0)pbu->llink=llink->cloneAll();
if(rlink.get()!=0)pbu->rlink=rlink->cloneAll();
return bu;
}
void UNode::show(std::string road,std::ostream&o){
o<<road<<this->key<<'\t'<<this->data<<'\n';
}
auto_ptr<BNode> CNode::clone(){
auto_ptr<BNode> bn((BNode*)new CNode);
((CNode*)bn.get())->count=this->count;
return bn;
}
auto_ptr<BNode> CNode::cloneAll(){
CNode *pbn;
auto_ptr<BNode> bn((BNode*)(pbn=new CNode));
pbn->key=this->key;
pbn->count=this->count;
if(llink.get()!=0)pbn->llink=llink->cloneAll();
if(rlink.get()!=0)pbn->rlink=rlink->cloneAll();
return bn;
}
void CNode::show(std::string road,std::ostream &o){
o<<road<<count<<"\t"<<key<<'\n';
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -