Underground - Bhasker V K,the Sandman's Hideout

Create a New Forum Admin Login Member Login Contribute to Voyager Search VoyForums Help Desk VoyForums Exchange VoyForums Directory/Categories VoyForums Homepage VoyForums News FAQ - Frequently Asked Questions

[ Show ]

Support VoyForums

[ Shrink ]

VoyForums Announcement: Programming and providing support for this service has been a labor of love since 1997. We are one of the few services online who values our users' privacy, and have never sold your information. We have even fought hard to defend your privacy in legal cases; however, we've done it with almost no financial support -- paying out of pocket to continue providing the service. Due to the issues imposed on us by advertisers, we also stopped hosting most ads on the forums many years ago. We hope you appreciate our efforts.

Show your support by donating any amount. (Note: We are still technically a for-profit company, so your contribution is not tax-deductible.) PayPal Acct: Feedback:

Donate to VoyForums (PayPal):

[ Login ] [ Contact Forum Admin ] [ Main index ] [ Post a new message ] [ Search | Check update time | Archives: 1 ]

Subject: Re: binary search Author: b [ Next Thread | Previous Thread | Next Message | Previous Message ] Date Posted: 18:30:05 09/21/05 Wed Author Host/IP: dsl-TN-024.246.247.61.touchtelindia.net/61.247.246.24 In reply to: b 's message, "binary search" on 18:27:42 09/21/05 Wed /*******Binary Search Tree Simulator v1.0****** This program simulates a binary search tree and performs elementary search operations on it. It includes the functionality to view the tree and also to free the tree.There is another function to optimise the binary search tree for maximum search efficiency.The function to delete a node from the tree allows deletion of all nodes but the root node.This program has been released to the public domain for academic purposes and for making improvements.Suggested improvements are an option to delete the root node of the tree and to make the view tree function better which I believe is pretty difficult.The globalpointer root holds always points to the root.Please do send me the improved versions of this program. Author:Deepak E-mail:deepak-p@eth.net Computer Engg: Student,Kerala,India. **********************************************/ # include /*Fordynamic memory allocation functions*/ # include # include struct node { int key; struct node *left; struct node *right; }; struct node *root,*t1,*t2; int count=0,arrcount=0,comp=0; int *array; void inittree(int i) { root=(struct node *)malloc(sizeof(struct node)); root->key=i; root->left=NULL; root->right=NULL; count++; } void add2tree(struct node *t,int i) { struct node *p; if((i>t->key)&&(t->right==NULL)) { p=(struct node *)malloc(sizeof(struct node)); p->key=i;p->left=NULL;p->right=NULL; t->right=p; return; } if((ikey)&&(t->left==NULL)) { p=(struct node *)malloc(sizeof(struct node)); p->key=i;p->left=NULL;p->right=NULL; t->left=p; return; } if(i>t->key)add2tree(t->right,i); else if(ikey)add2tree(t->left,i); } void inorder(struct node *t)/*Inorder traversal of the tree***/ { if(t==NULL)return; inorder(t->left); printf("\n%d",t->key); inorder(t->right); } /*****Set arrcount (global)to 0 before calling this function****/ void print2array(struct node *t) { if(t==NULL)return; print2array(t->left); array[arrcount]=t->key; arrcount++; print2array(t->right); } /******Set arrcount(global)to 0 before calling this function*****/ void getno(struct node *t)/*To get no of elements*/ { if(t==NULL)return; getno(t->left); arrcount++; getno(t->right); } void freetree(struct node *t) { if(t==NULL)return; if(t->left!=NULL)freetree(t->left); if(t->right!=NULL)freetree(t->right); t->right=NULL;t->left=NULL;t=NULL;t->key=NULL; free(t); } struct node *makeoptree(int *arr,int a,int b)/*Tree optimiser*/ { struct node *t1,*t2; int n=b-a+1; if(n==1) { t2=(struct node *)malloc(sizeof(struct node)); t2->key=arr[a]; t2->left=NULL; t2->right=NULL; return t2; } if(n==0) { return NULL; } t1=(struct node *)malloc(sizeof(struct node)); t1->key=arr[(int)(a+n/2)]; t1->left=makeoptree(arr,a,(int)(a+n/2-1)); t1->right=makeoptree(arr,(int)(a+n/2+1),b); return t1; } int search(struct node *t,int i) { comp++; if(i==t->key){return 1;} if((ikey)&&(t->left==NULL)){return 0;} if((i>t->key)&&(t->right==NULL)){return 0;} if(ikey){return search(t->left,i);} if(i>t->key){return search(t->right,i);} return 0; } void callsearch() { int i,j; printf("\nEnter an element to be searched:"); scanf("%d",&i); comp=0; j=search(root,i); if(j==1) { printf("\nFound after %d comparisons\n\n",comp); return; } else if(j==0) { printf("\nCould not find after %d comparisons\n\n",comp); return; } } void viewtree(struct node *t,int x,int y) { if(t==NULL)return; gotoxy(x,y); printf("%d",t->key); viewtree(t->left,x-4,y+1); viewtree(t->right,x+4,y+1); } struct node *getparent(struct node *t,int i) { int n=search(t,i); if(n==0) { return NULL; } if((i>t->key)&&(i==t->right->key)) {return t;} else if(i>t->key) {return getparent(t->right,i);} if((ikey)&&(i==t->left->key)) {return t;} else if(ikey) {return getparent(t->left,i);} return NULL; } struct node * getnode(struct node *t,int i) { if(search(t,i)==0)return NULL; if(t->key==i)return t; else if(i>t->key)return getnode(t->right,i); else if(ikey)return getnode(t->left,i); return NULL; } struct node *getsuccessor(int i) { struct node *a; int j,len; if(search(root,i)==0)return NULL; arrcount=0;getno(root);len=arrcount; array=(int *)calloc(len,sizeof(int)); arrcount=0;print2array(root); for(j=0;j<(len-1);j++) { if(i==array[j]) { a=getnode(root,array[j+1]); free(array); } } if(i==array[len-1]) { free(array); return NULL; } return a; } int deleteitem(int i) { struct node *a,*b,*c,*d; a=getnode(root,i); b=getparent(root,i); c=getsuccessor(i); if(search(root,i)==0) return -1; if((a->left==NULL) && (a->right==NULL)) { if(b->right==a)b->right=NULL; else b->left=NULL; a=NULL; free(a); return 0; } else if((a->left!=NULL)&&(a->right==NULL)) { if(b->left==a) b->left=a->left; else b->right=a->left; a=NULL; free(a); return 0; } else if((a->right!=NULL)&&(a->left==NULL)) { if(b->left==a) b->left=a->right; else b->right=a->right; a=NULL; free(a); return 0; } } int intro() { int i; clrscr(); printf("Binary Search Tree Simulator 1.0\n\n\n"); printf("\n1.Add Items to the tree"); printf("\n2.View the tree"); printf("\n3.Optimise tree"); printf("\n4.Search for an element"); printf("\n5.Free the tree"); printf("\n6.Input an element to get parent"); printf("\n7.Delete an item"); printf("\n8.Input an element to get successor"); printf("\n9.Exit\n"); printf("\nEnter your response:"); scanf("%d",&i); fflush(stdin); clrscr(); return i; } main() { int i,n; abc: i=intro(); if(i==1) { printf("\nEnter the element to be added to the tree:"); scanf("%d",&n);fflush(stdin); arrcount=0;getno(root); if(arrcount==0){inittree(n);} else {add2tree(root,n);} goto abc; } else if(i==2) { clrscr(); arrcount=0;getno(root); if(arrcount==0){printf("\nEmpty tree");} else{viewtree(root,38,1);} getch(); goto abc; } else if(i==3) { arrcount=0;getno(root); array=(int *)calloc(arrcount,sizeof(int)); arrcount=0; print2array(root); freetree(root); root=makeoptree(array,0,arrcount-1); printf("\nTree optimisation finished");getch(); free(array); goto abc; } else if(i==4) { callsearch(); getch(); goto abc; } else if(i==5) { freetree(root);root=NULL; printf("\nBinary tree has been freed"); getch(); goto abc; } else if(i==6) { printf("\nEnter an element to find the parent:"); scanf("%d",&n);fflush(stdin); t1=getparent(root,n); if(t1!=NULL) printf("\nParent is %d",t1->key); else printf("\nElement not present or is the root"); getch(); goto abc; } else if(i==7) { printf("\nEnter an element to delete:"); scanf("%d",&n); if(search(root,n)==0) printf("\nElement not present"); else { deleteitem(n); printf("\nItem deleted"); } getch(); goto abc; } else if(i==8) { printf("\nEnter an element to find successor:"); scanf("%d",&n);fflush(stdin); t1=getsuccessor(n); if(t1==NULL) printf("\nElement not present or has no successor"); else printf("\nSuccessor is %d",t1->key); getch(); goto abc; } else if(i==9) { printf("\nThank you"); getch(); exit(0); } return; } [ Next Thread | Previous Thread | Next Message | Previous Message ]

Replies:

[> [> Subject: Re: binary search Author: linked list [ Edit | View ] Date Posted: 18:35:01 09/21/05 Wed Author Host/IP: dsl-TN-024.246.247.61.touchtelindia.net/61.247.246.24 #include #include #include #include /* **************************************************************** CODE WRITTEN BY NADIA MIJA, MARCH 27, 2003, BUCHAREST,ROMANIA **************************************************************** You can use this code for any purpuses except publication or selling. **************************************************************** 1) TNODE -- the list nodes type; - lkey -- list key = a value which is different for each node of the list; it can be useful for some applications it's recommendended to use it - name - a string information used only for example; here must be the real information of the list - next - the next node pointer; 2) void CreateList() -- creates a list; for any TNODE structure (general function) 3) void ViewAllList() -- shows the list items for any TNODE structure (general function); 4) void DeleteList() -- removes completely the entire list ; (general function) 5) TNODE* FindNode(int key) -- returns a pointer to a list-node which has the lkey-value equal-to key-parameter; (general function) 6) TNODE* InsertAfterKey(int key) -- inserts a new node (list item) after a list-node which has the lkey-value equal-to key-parameter; (general function) 7) TNODE* InsertAfterLast() -- inserts a new node (list item) after the last-node of the list ; (general function) 8) TNODE* InsertBeforeFirst() -- inserts a new node (list item) before the first-node of the list; (general function) 9) TNODE* InsertBeforeKey(int key) -- inserts a new node (list item) before a list-node which has the lkey-value equal-to key-parameter; (general function) 10) void RemoveByKey(int key) -- removes a list-node which has the lkey-value equal-to key-parameter; (general function) 11) void RemoveFirst() -- removes the first node of the list; (general function) 12) void RemoveLast() -- removes the last node of the list; (general function) I ALSO HAVE WRITTEN A FEW FUNCTIONS WHICH ARE DEPENDENT TO THE TNODE STRUCTURE; THEY NEED TO BE REWRITTEN FOR EVERY APPLICATION 1) void FreeNode(TNODE *p)//function specific to the application -- deallocates the memory for the p node 2) int LoadNode(TNODE *p) //function specific to the application -- loads the information into the nodes of the list but should always return these values 0 - Error 1 - ok; -1 - no more data to load In this case (meaning my function) you shuld reply - anything for yes - n/N for no 3) void PrintNode(TNODE *p) //function specific to the application -- shows the information of the p node PLEASE ALSO READ THE COMMENTS IN THE CODE FOR MORE INFORMATION **************************************************************** */ typedef struct node { int lkey; //key node char name[10]; //specific to the application; node's information struct node* next; } TNODE; TNODE *first, *last; //pointers to the first and last element of the linked list int LoadNode(TNODE *p); void FreeNode(TNODE *p); void PrintNode(TNODE *p); void CreateList() //this function can be used no matter what the structure TNODE looks like { // meaning it can be used for any type of applications concerning lists TNODE *p; //general function int n=sizeof(TNODE); first=last=0; //empty list for(;;) { if( (p=(TNODE*)malloc(n))==0 ) //allocation could not be made { printf("\nNot enough memory"); break; } if(LoadNode(p)!=1) { FreeNode(p); break; } p->next=0; if (first==0) //this list was empty since now first=last=p; else { last->next=p; last=p; } } } int LoadNode(TNODE *p) //function specific to the application { //but should always return these values /* 0 - Error 1 - ok; -1 - no more data to load */ char opt; printf("\nNew node?"); opt=getche(); opt=toupper(opt); if(opt!='N') { puts("\nPlease insert data for the current node:"); printf("\nlkey:\t"); if (scanf("%d",&(p->lkey))!=1) return 0; //could not read lkey value for current node printf("\nname:\t");if (scanf("%s",p->name)!=1) return 0; return 1; } else return -1; } void FreeNode(TNODE *p)//function specific to the application { free(p); } void ViewAllList()//general function { TNODE *p; p=first; while(p) { PrintNode(p); p=p->next; } } TNODE* FindNode(int key) //general function //serches and returns the node having the lkey value equal to the key parameter { TNODE *p; p=first; while(p) { if(p->lkey == key) return p; p=p->next; } return 0; //value not found } void PrintNode(TNODE *p) //function specific to the application { if(p) printf("\n%d\t%s",p->lkey,p->name); } TNODE* InsertBeforeFirst() //general function //returns the node inserted //or 0 for failed insertion { TNODE *p; int n=sizeof(TNODE); if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded { if (first==0) //list was empty { p->next=0; first=last=p; } else { p->next=first; first=p; } return p; } if(p==0) //not enough memory printf("\nNot enough memory"); else //the node could not be loaded FreeNode(p); return 0; //there is no node inserted before first -- insertion failed } TNODE* InsertBeforeKey(int key) //general function //returns the node inserted //or 0 for failed insertion { TNODE *p, *q, *q1; //p=the new node to insert //q=key //q1=the node before key int n=sizeof(TNODE); //find q, q1 q1=0; q=first; while(q) { if(q->lkey == key) break; //key node found q1=q; //keep on searching for key node q=q->next; } if(q==0) { printf("\nThere is no node having such a key or the list is empty");//this case also includes the case of empty list return 0;//there is no node having such a key -- insertion can't be made } //now the key was found -- so we try to make the insertion if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded { if(q==first) //we have to insert before the first node { p->next=first; first=p; } else //the key node is not the first one { p->next=q; q1->next=p; } return p; } if(p==0) //not enough memory printf("\nNot enough memory"); else //the node could not be loaded FreeNode(p); return 0; //there is no node inserted before key -- insertion failed } TNODE* InsertAfterKey(int key) //general function //returns the node inserted //or 0 for failed insertion { TNODE *p, *q; //p=the new node to insert //q=key int n=sizeof(TNODE); //find q q=first; while(q) { if(q->lkey == key) break; //key node found q=q->next; //keep on searching for key node } if(q==0) { printf("\nThere is no node having such a key or the list is empty");//this case also includes the case of empty list return 0;//there is no node having such a key -- insertion can't be made } //now the key was found -- so we try to make the insertion if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded { if(q==last) //we have to insert after the last node { p->next=0; last->next=p; last=p; } else //the key node is not the last one { p->next=q->next; q->next=p; } return p; } if(p==0) //not enough memory printf("\nNot enough memory"); else //the node could not be loaded FreeNode(p); return 0; //there is no node inserted after key -- insertion failed } TNODE* InsertAfterLast() //general function //returns the node inserted //or 0 for failed insertion { TNODE *p; int n=sizeof(TNODE); if (((p=(TNODE*)malloc(n))!=0) && (LoadNode(p)==1)) //a new node has been succesfully allocated and loaded { p->next=0; if (first==0) //list was empty first=last=p; else { last->next=p; last=p; } return p; } if(p==0) //not enough memory printf("\nNot enough memory"); else //the node could not be loaded FreeNode(p); return 0; //there is no node inserted after last -- insertion failed } void RemoveFirst() //general function //removes the first node of the list; pre and post-conditions: none { TNODE *p; if(first==0)//list was empty return; if(first==last)//there is just one node { FreeNode(first); first=last=0; return; } p=first; first=first->next; FreeNode(p); } void RemoveLast() //general function //removes the last node of the list; pre and post-conditions: none { TNODE *p, *q; if(first==0)//list was empty return; if(first==last)//there is just one node { FreeNode(first); first=last=0; return; } q=0;//there are at least 2 nodes p=first; while(p!=last) { q=p; p=p->next; }//so we have q=the node before the last one p=last;//now we're going to remove the last node FreeNode(p); q->next=0; last=q; } void RemoveByKey(int key) { TNODE *p, *q; //p - the key node //q=the node before the key node if(first==0)//list was empty return; q=0;//there are at least 2 nodes p=first; while(p) { if(p->lkey == key) break; //key node found q=p; p=p->next; }//so we have q=the node before the key one; p=key node if(!p)//There is no node having such a key { printf("\nThere is no node having such a key"); return; } if(first==last)//there is just one node which is the key node { FreeNode(first); first=last=0; return; } if(p==first) //first is the key node { first=first->next; FreeNode(p); return; } if(p==last) // last was the key node { q->next=0; last=q; FreeNode(p); return; } q->next=p->next; FreeNode(p); } void DeleteList() { TNODE *p; p=first; while(p) { first=first->next; FreeNode(p); p=first; } last=0; } void main() { CreateList();//this is an example of using these fonctions ViewAllList(); InsertAfterLast(); ViewAllList(); RemoveFirst(); ViewAllList(); InsertAfterKey(1);//by example ViewAllList(); RemoveByKey(1); ViewAllList(); DeleteList(); ViewAllList(); } [ Post a Reply to This Message ]

[> [> [> Subject: Re: binary search Author: binar search tree implementation [ Edit | View ] Date Posted: 18:37:06 09/21/05 Wed Author Host/IP: dsl-TN-024.246.247.61.touchtelindia.net/61.247.246.24 //Binary search tree implementation by Niranjan Yadla #include #include struct node { int data; struct node *left; struct node *right; }; void binsearchtree(struct node **,int); void delatgivendata(struct node **,int); inorder(struct node *); preorder(struct node *); postorder(struct node *); void main() { int data,choice; struct node *p; p=NULL; clrscr(); while(1) { printf("\n1.Add node to the binary search tree"); printf("\n2.Deletion at given data:"); printf("\n3.Exit"); printf("\nEnter the choice"); scanf("%d",&choice); switch(choice) { case 1: printf("\nEnter the data"); scanf("\n%d",&data); binsearchtree(&p,data); printf("\n The inorder traversals are:"); printf("\n"); inorder(p); printf("\n The preorder traversals are:"); printf("\n"); preorder(p); printf("\nThe post order traversals are:"); printf("\n"); postorder(p); break; case 2: printf("\n Please enter the data where you want deleted"); scanf("%d",&data); delatgivendata(&p); printf("\nThe inorder traversals are :"); inorder(p); break; case 3:exit(0); } } } void binsearchtree(struct node **q,int data) { struct node *temp,*r; r=*q; temp=(struct node*)malloc(sizeof(struct node)); temp->data=data; temp->left=NULL; temp->right=NULL; if(r==NULL) { *q=temp; (*q)->left=temp->left; (*q)->right=temp->right; } else { if(r->data==data) printf("\nInvalid input\n"); while(1) { if(r->data>data) { if(r->left==NULL) { r->left=temp; break; } r=r->left; } else { if(r->right==NULL) { r->right=temp; break; } r=r->right; } } } } void delatgivendata(struct node **q,int data) { struct node *r; r=*q; } inorder(struct node *q) { struct node *r; r=q; if(r==NULL) return 0; else { inorder(r->left); printf("%d\t",r->data); inorder(r->right); } } preorder(struct node *q) { struct node *r; r=q; if(r==NULL) return 0; else { printf("%d\t",r->data); preorder(r->left); preorder(r->right); } } postorder(struct node *q) { struct node *r; r=q; if(r==NULL) return 0; else { postorder(r->left); postorder(r->right); printf("%d\t",r->data); } } [ Post a Reply to This Message ]