异质树的实现--C++实现

/*************************************************** 异质树建立，遍历，查找，插入，删除的实现 所谓异质树，就是一棵树，树是由类型各不相同的节点组成。 2008/11/10 FileName: main.cpp ****************************************************/ #include "main.h" /*************************************************** //Description: the main entrance //Parameters: int argc,char *argv[] //Return: int ****************************************************/ int main(int argc, char *argv[]) { char type; char operation; char nm[LENGTH]; char ID[LENGTH]; int N; Person *Plist=NULL,*pc=NULL,*pmove=NULL; cout<<"Please input the number of node in the tree? N="; cin>>N; cout<<"Please input data as:"<<"type "<<"name "<<"ID "<<endl; cout<<"(type:p-person,s-student,t-teacher)"<<endl; for(int i=0;i<N;i++) { memset(nm,0,sizeof(nm)); memset(ID,0,sizeof(ID)); cin>>type>>nm>>ID; switch(type) { case'p': pc=new Person(nm,ID); pc->lchild=NULL; pc->rchild=NULL; break; case't': pc=new Teacher(nm,ID); pc->lchild=NULL; pc->rchild=NULL; break; case's': pc=new Student(nm,ID); pc->lchild=NULL; pc->rchild=NULL; break; default: break; } if(Plist==NULL) { Plist=pc; pmove=pc; } else { pmove=Plist; while(1) { //compare with the root if(strcmp(pc->ptrnm(),pmove->ptrnm())<0){ if(pmove->lchild!=NULL) pmove=pmove->lchild; else { pmove->lchild=pc; break; } }else{ if(pmove->rchild!=NULL) pmove=pmove->rchild; else { pmove->rchild=pc; break; } } } } } traverse_display(Plist); cout<<"These operations can be done now\n"; int running = 1; while(running) { cout<<" 1. traverse the tree "<<endl; cout<<" 2. search one node "<<endl; cout<<" 3. delete one node "<<endl; cout<<" 4. insert one node "<<endl; cout<<" 5. quit"<<endl; cin>>operation; switch(operation) { case('1'): traverse_display(Plist); break; case('2'): search(Plist); break; case('3'): { Person *parent=NULL,*pc=NULL; pc=search(Plist); if(pc==NULL) { break; } cout<<pc->ptrnm()<<" has been delete! "<<endl; parent=get_parent(Plist,pc->ptrnm()); Plist=del_node(Plist,pc,parent); break; } case('4'): { char type; char name[LENGTH]; char ID[LENGTH]; cout<<"===================================================="<<endl; cout<<"Please input the node data:(type name ID)\n"; cin>>type>>name>>ID; switch(type) { case('p'): pc=new Person(name,ID);pc->lchild=NULL;pc->rchild=NULL;break; case('t'): pc=new Teacher(name,ID);pc->lchild=NULL;pc->rchild=NULL;break; case('s'): pc=new Student(name,ID);pc->lchild=NULL;pc->rchild=NULL;break; default: break; } Plist=insert(Plist,pc); traverse_display(Plist); break; } case('5'): quit(); running = 0; break; default: break; } } system("PAUSE"); return 0; } /*************************************************** //Description: Traverse the tree,and display them //Parameters: Person *ptemp //Return: NULL ****************************************************/ void traverse_display(Person *ptemp) { Person *que[PRT_NUM],*p=ptemp,*t=ptemp; int front,rear,num=0; cout<<"===================================================="<<endl; if(t!=NULL) { que[0]=t; front=-1; rear=0; } while(front<rear) { p=que[++front]; p->prt(); num++; if(p->lchild!=NULL) que[++rear]=p->lchild; if(p->rchild!=NULL) que[++rear]=p->rchild; } cout<<"there are "<<num<<" nodes in the tree \n"; cout<<"===================================================="<<endl; } /*************************************************** //Description: search one of the node //Parameters: Person *ptemp //Return: Person * ****************************************************/ Person * search(Person *ptemp) { char sname[LENGTH]; Person *pmove=ptemp; cout<<"===================================================="<<endl; cout<<"Input the name of node:"; cin>>sname; while(pmove!=NULL) { if(strcmp(pmove->ptrnm(),sname)==0) { cout<<"find the node,info:"<<endl; pmove->prt(); cout<<"===================================================="<<endl; return pmove; } if(strcmp(sname,pmove->ptrnm())<0) { pmove=pmove->lchild; } else { pmove=pmove->rchild; } } cout<<"can't find the name :"<<sname<<endl; cout<<"===================================================="<<endl; return NULL; } /*************************************************** //Description: insert one node //Parameters: Person *Plist,Person *pc //Return: Person * ****************************************************/ Person * insert(Person *Plist,Person *pc) { if(Plist==NULL) { Plist=pc; } else { Person *pmove; pmove=Plist; while(1) { if(strcmp(pc->ptrnm(),pmove->ptrnm())<0){ if(pmove->lchild!=NULL) pmove=pmove->lchild; else { pmove->lchild=pc; break; } }else{ if(pmove->rchild!=NULL) pmove=pmove->rchild; else { pmove->rchild=pc; break; } } } } return Plist; } /*************************************************** //Description: get the parent node of one node //Parameters: Person *ptemp,char *sname //Return: Person * ****************************************************/ Person* get_parent(Person *ptemp,char *sname) { Person *pmove=ptemp; Person *parent=NULL; if(strcmp(pmove->ptrnm(),sname)==0) return parent; while(pmove!=NULL) { if(strcmp(pmove->ptrnm(),sname)==0) { return parent; } if(strcmp(sname,pmove->ptrnm())<0) { parent=pmove; pmove=pmove->lchild; } else { parent=pmove; pmove=pmove->rchild; } } cout<<"can't find the name :"<<sname<<endl; return NULL; } /*************************************************** //Description: delete one node //Parameters: Person *Plist,Person *pc,Person *parent //Return: Person * ****************************************************/ Person * del_node(Person *Plist,Person *pc,Person *parent) { Person *r=NULL,*s=NULL; int flag=0; if(pc->rchild==NULL){ if(pc==Plist) Plist=pc->lchild; else { r=pc->lchild; flag=1; } }else if(pc->lchild==NULL){ if(pc==Plist) Plist=pc->rchild; else { r=pc->rchild; flag=1; } }else{ s=pc; r=s->rchild; while(r->lchild!=NULL) { s=r; r=r->lchild; } r->lchild=pc->lchild; if(s!=pc) { s->lchild=r->rchild; r->rchild=pc->rchild; } if(pc==Plist) Plist=r; else flag=1; } if(flag==1){ if(pc==parent->lchild) parent->lchild=r; else parent->rchild=r; } delete pc; traverse_display(Plist); return Plist; } /*************************************************** //Description: insert one node //Parameters: Person *Plist,Person *pc //Return: Person * ****************************************************/ void quit() { cout<<"===================================================="<<endl; cout<<"Quit from this program!"<<endl; cout<<"===================================================="<<endl; }