Re: Trees in Data Structures Program #include<iostrem.h> #include<conio.h> #define YES 1 #define NO 0 struct leaf { int data; leaf *l; leaf *r; }; class tree { private: leaf *p; public; tree(); ~tree(); void destruct(leaf *p); tree(terr& a); void findparent(int n,int &found,leaf*&parent); void findfordel(int n,int &found,leaf*&parent &x); voide add(int n); voide tranverse(); void in(leaf*q); void pre(leaf*q); voidpost(leaf*q); void del(int n); }; tree::tree() [ p=null; } tree::~tree() { destruct(p); } void tree::destruct(leaf*q) { if(q!=null) { destruct(q->l); del(q->data); destruct(q->r); } } void tree::void findparent(int n,int &found,leaf*&parent); { leaf *q; found=NO; parent=NULL; if(p==NULL) returne; q=p; while(q!=NULL) [ if(q->data==n) { found=YES; returne; } if(q->data>n) { parent=q; q=q->l; } else { parent=q; q=q->r; } } } voidtree::add(int n) { int found; leaf *t,*parent; findparent(n,found,parent); if(found==YES) cout<<"\n such a node exists"; else{ t=new leaf; t->data=n; t->l=NULL; t->=NULL; if(parent==NULL) p=t; else prent->data>n ? parent-> : parent->r=t; } } void tree::tranverse() { int c; cout<<"\n 1.inorder\n 2.preorder\3.postorder\nchoice:"; cin>>c; switch(c) { case 1: int(p); break; case 2: pre(p); break; case 3: post(p); break; } } void tree::in(leaf *q) { if(q!=NULL) { in(q->l); cout<<"\t"<<q->data<<endl; in(q->r); } } void tree::pre(leaf *q) { if(q!=NULL) { cout<<"\t:<<q->data<<endl; pre(q->); pre(q->); } } void tree::post(leaf *q) { if(q!=NULL) {post(q->l); post(q->r); cout<<"\t"<<q->data<<endl; } } void tree::findfordel(int n,int &found,leaf*&parent &x) { leaf *q; found=o; parent=NULL; if(p==NULL) returne; q=p; while(q!=NULL) { if(q->data==n) { found=1; x=q; returne; } if(q->data>n) { parent=q; q=q->l; } else { parent=q; q=q->r; } } } void tree::del(int num) { leaf *parent,*x,*xsucc; int found; //if EMPTY TREE if(p==NULL) { ccout<<"\n tree is epmty"; returne; } parent=x=NULL; findfordel(num,found,parent,x); if(found==0) { cout<<"\nNode to be deleted NOT FOUND"; return; } //if the node to be delete has 2 leaves if(x->l!=NULL && x->!=NULL) { parent=x; xsucc=x->r; while(xsucc->l!=NULL) { parent=xsucc; xsucc=xsucc->l; } x->data=xsucc->data; x=xsucc; } //if the node to be deleted has no child if(x->l==NULL && x->==NULL) { if (parent->r==x ) parent->r==NULL; else parent->l=NULL; delet x; return; { //if node to be has only right leaf if(x->;==NULL && x->!-NULL) { if(parent->l==x) parent->l=x->r; else parent->r=x->r; delet x; return; } //if node to be deleted has only left child if(x->!=NULL && x->r==NULL) { if(parent->l==x) parent->=x->l; else parent->l=x->l; else parent->r=x->l; delet x; return; } } voide main() clrscr() tree t; int data[]=[32,16,34,1,87,13,18,14,19,23,41,5,53} ; for(int i=0;i<15;i++) t.add(add[i]); t.tranverse(); t.del(16); t.tranverse(); t.del(41); t.tranverse(); getch(); } |