Binary trees search problem...

Umoniel · 02-22-2004, 12:13 PM

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);
		}

Edward · 02-22-2004, 02:15 PM

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.

Umoniel · 02-22-2004, 02:29 PM

Thanks you solved my problem, big big thanks !

02-22-2004, 02:15 PM	#2
Edward 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.
Edward is offline

02-22-2004, 02:29 PM	#3
Umoniel Registered User Join Date: Nov 2002 Posts: 4	Thanks you solved my problem, big big thanks !
Umoniel is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

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