Thread: Binary trees search problem...

  1. #1
    Registered User
    Join Date
    Nov 2002
    Posts
    4

    Binary trees search problem...

    Hello all i'm working for school on a binary tree.
    I've made inseriment, simmetric visit, preorder visit, postorder visit and a search function.
    The tree is balanced and the search function gets a number and gives as output the number of the node the number is in.
    Of course all with recursion.
    The teacher wants us to complete the program so if there isn't the number you are searching there's an out like "no number found".
    I can't do it with a global variable, i've tried with returns but i really can't understand how to implement this well, if anyone can help....
    Here's the code, sry for confusing names but i'm italian...

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<string.h>
    #include<alloc.h>
    struct info{ int valore;
    			 struct info *sx;
    			 struct info *dx;
    		   };
    struct info *primo=NULL;
    
    void collegamento(struct info *, struct info *);
    void simmetrico(struct info *);
    void preordine(struct info *);
    void postordine(struct info *);
    void ricerca(int, int, struct info *);
    
    void inserimento(void){
    			   struct info *nuovo;
    			   nuovo=malloc(sizeof(struct info));
    			   printf("Inserisci il valore:\n");
    			   scanf("%d",&nuovo->valore);
    			   nuovo->sx=NULL;
    			   nuovo->dx=NULL;
    			   if(primo==NULL) primo=nuovo;
    			   else	collegamento(nuovo,primo);
    			   }
    
    void collegamento(struct info  *dac, struct info  *attuale){
    		  if(dac->valore < attuale->valore){
    						  if(attuale->sx==NULL) attuale->sx=dac;
    						  else collegamento(dac,attuale->sx);
    						  }
    		  if(dac->valore > attuale->valore){
    						  if(attuale->dx==NULL) attuale->dx=dac;
    						  else collegamento(dac,attuale->dx);
    						  }
    			   }
    
    void simmetrico(struct info *elemento){
    						 if(elemento!=NULL){
    								 simmetrico(elemento->sx);
    								 printf("Il valore Š %d\n",elemento->valore);
    								 simmetrico(elemento->dx);
    								 }
    						 }
    
    void preordine(struct info *elemento){
    						 if(elemento!=NULL){
    								 printf("Il valore Š %d\n",elemento->valore);
    								 preordine(elemento->sx);
    								 preordine(elemento->dx);
    								 }
    						 }
    
    void postordine(struct info *elemento){
    						 if(elemento!=NULL){
    								 postordine(elemento->sx);
    								 postordine(elemento->dx);
    								 printf("Il valore Š %d\n",elemento->valore);
    								 }
    						 }
    void ricerca(int valore, int nnodo, struct info *elemento){
    						 if(elemento!=NULL){
    								 if(elemento->valore==valore){
    									printf("Nodo %d",nnodo);
    									getch();
    									}
    								 nnodo++;
    								 ricerca(valore,nnodo,elemento->sx);
    								 ricerca(valore,nnodo,elemento->dx);
    							 }
    						 nnodo--;
    					}
    
    
    char sc;
    int valz;
    
    void main(){
    	   do{
    		  clrscr();
    		  printf("1)Inserimento\n2)Simmetrico\n3)Preordine\n4)Postordine\n");
    		  sc=getch();
    		  switch(sc){case '1':inserimento();
    							  break;
    					 case '2':simmetrico(primo);
    							  getch();
    							  break;
    					 case '3':preordine(primo);
    							  getch();
    							  break;
    					 case '4':postordine(primo);
    							  getch();
    							  break;
    					 case '5':printf("Inserisci il valore da cercare\n");
    							  scanf("%d",&valz);
    							  ricerca(valz,0,primo);
    							  break;
    					}
    		   }while(sc!=27);
    		}

  2. #2
    Registered User
    Join Date
    Feb 2004
    Posts
    46
    A search routine will typically choose one of two choices for return value: the item that was found, or a success/failure code. Which is better is a matter of personal style, but if you want both a success/failure code and the item that was found on success you will need to use an out parameter.
    Code:
    int search(struct node *sub, int item, struct node *found)
    {
        if (sub == NULL)
            return 0;
        else if (item < sub->data)
            return search(sub->left, item, found);
        else if (item > sub->data)
            return search(sub->right, item, found);
        else {
            found = sub;
            return 1;
        }
    }
    In this function, 0 is returned if the item isn't found, 1 if it is. So the function call can be used in a boolean expression. The out parameter is called found. Its only purpose is to save the item if it was found so that it might be used by the caller. A reasonable call might look like this.
    Code:
    struct node *found;
    if (search(tree, key, found))
        process_data(found);
    Many search functions use an invalid item as the return value for failure. Such a value in a tree would likely be NULL or a dummy node used for leaves. In this way you can forgo the extra out parameter.
    Code:
    struct node *found = search(tree, key);
    if (found != NULL)
        process_data(found);
    That being said, recursive functions have a tendency to make useful return values difficult to implement.

  3. #3
    Registered User
    Join Date
    Nov 2002
    Posts
    4
    Thanks you solved my problem, big big thanks !

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. problem in storing data in a binary search tree
    By alavardi in forum C Programming
    Replies: 5
    Last Post: 02-13-2005, 03:20 PM
  2. Problem with fprintf and binary search.
    By tallgeese84 in forum C Programming
    Replies: 4
    Last Post: 12-06-2004, 09:37 PM
  3. STL and Binary Search Trees
    By xshapirox in forum C++ Programming
    Replies: 2
    Last Post: 11-29-2004, 12:12 PM
  4. Problem with binary search tree :(
    By Unregistered in forum C Programming
    Replies: 10
    Last Post: 05-01-2002, 10:31 PM
  5. Newbie questions regarding binary search trees
    By Ham in forum C++ Programming
    Replies: 1
    Last Post: 11-04-2001, 07:48 AM