Allora ho una struttura albero che puo avere max 3 figli....
Il mio problema è implementare una funzione cerca(che ha come parametro la radice dell'albero e il valore da cercare) che mi restituisca un puntatore all'elemento che stavo cercando....
Non essendo un albero binario di ricerca ho parecchi problemi a eseguire la ricerca...
grazie sarò eternamente grato a chi mi aiuterà...
intanto vi metto anche la struttura....
typedef struct Nodo
{
int x,y;
struct Nodo *f1,*f2,*fi3,*padre;
}ALBERO;
cosi', a orecchio() credo sia sufficiente fare una chiamata ricorsiva per ciascun figlio.............cmq puo' essere pure che mi sbaglio!
ora ci penso un po e ti dico!
Se sai farlo con un albero binario allora devi per forza saperlo fare anche con un albero ternario strutturato in quel modo.
allora...come ti dicevo fai una chiamata ricorsiva per ciascun figlio!
ti scrivo l'algoritmo:
supponenodo di avere una struttura del genere
struct nodo{
int info;
nodo* dx,*centrale,*sx,*padre;
}; l'algo CERCA e' il seguente:
CERCA(punt,valore,flag)
if (!punt) return NULL
if (punt->info==valore) flag=true, return punt
return_value=CERCA(punt->dx,valore,flag)
if (!flag)
return_value=CERCA(punt->centrale,valore,flag)
if (!flag)
return_value=CERCA(punt->sx,valore,flag)
return return_value
Il problema grosso e' che nel caso pessimo(cioe' nel caso in cui il valore desiderato e' nella foglia in fondo a destra)la complessita' dell'algoritmo e' molto alta perche' passa per tutti i nodi dell'albero(in generale e' 3*n+1 dove n e' il numero di nodi)!
Per ovviare a cio occorrerebbe costruire l'albero in modo 'furbo'.....e la complessita' nel caso pessimo diminuirebbe di parecchio [ O(h) dove h e' l'altezza dell'albero ]
ti faccio un piccolo esempio:
in un albero (come il tuo) a 13nodi con una costruzione casuale l'algo potrebbe avere complissita' nel caso pessimo=3*13+1
in un albero a costruzione 'furba' =13
cmq forse mi sono dilungato un po' troppo
Sei un grande Zalex...
dovrei tenere conto anche della complessità computazionale...ma adesso come adesso preferisco farlo andare...provo ad implementarlo seguendo i tuoi consigli...
GRAZIEEEEEEEEEEEEEEEEEE
di niente.....ricordati di passare flag per riferimento altrimenti va tutto a puttane :metallica
bye
PS per qualsiasi cosa fai un fiskio
scusami zalex magari faccio una considerazione banale...ma nn dovrei sostituire il primo if(!punt) con un while?ho l'impressione che se lascio l'if mi controlli solo i primi tre figli....:master:e nn prendo in considerazione i figli dei figli...
Illuminami please
allora il primo if(!punt) ha le seguenti funzioni:
1)alla prima chiamata della funzione cerca, if(!punt) si traduce in italiano come "se l'lbero e' vuoto non fare nulla",infatti ritorna NULL
2)nelle varie chiamate ricorsive invece quel controllo risulta essere sempre falso finche non si arriva a un nodo che non ha un determinato filglio ,infatta supponiamo che il nodo N non abbia figlio dx(e naturalmente che l'info del nodo N non e' il valore che cerchi)allora if(!punt)risulta falso e va avanti....info non e' quello che cerci e va avanti......a questo punto richiama la funzione cerca col puntatore al figlio dx!bene qusto puntatore in effetti e' nullo xke N non ha filgio dx quindi quel controllo risulta vero e la funzione ritorna ...(l'attenzione ritorna al nodo N)a questo punto il flag e' ancora falso e viene richiamata la funzione cerca col punt al figlio centrale......e cosi' via
vengono percorsi tutti i nodi non soli i figli della radice xche ciascun nodo richiama a sua volta la funzione su ciascun suo figlio che a sua volta la richiama su ciascun suo figlio....finche qualche stronzo di nodo finalmente non avra' figli.....
spero di essere stato abbastanza chiaro........in caso contrario fammi sapere che ti preparo un disegnino.....e' piu' facile spiegarlo con un disegno
ciao
Permessi di invio
Rispondi quotando