[C] Albero binario, visite e ricerche

[draganbao]

Ciao a tutti
volevo chiedervi se gentilmente potreste risolvere un mio quesito:

avendo caricato in un albero binario delle struct, corrispondenti a dei prodotti e fatte in questo modo:

struct prodotto{
char codice[6]; //codice prodotto
int quantita; //quantità disponibile
int venduti; //pezzi venduti
struct prodotto *left;
struct prodotto *right;
}

come faccio a ricercare nell'albero quel prodotto che è stato maggiormente venduto (ovvero quello che ha il valore maggiore del campo venduti)

Potreste indicarmi una semplice funzione in c che effettui la visita dell'albero e mi restituisca il nodo cercato o alternativamente stampi a video il codice del prodotto più venduto?

Vi ringrazio,

Draganbao

[{Bl4d3}]

1) L'albero è ordinato? Se si, secondo che criterio?
2) Ma ci hai provato a farla questa funzione?

[draganbao]

Si certo...l'albero è ordinato rispetto alla chiave che è: codice

Certo che ho provato a fare la funzione e alla fine l'ho fatta in questo modo...

void trovaArticoloPiuVenduto(struct prodotto *radice){
if(radice != NULL){
trovaArticoloPiuVenduto(radice->left);
if(radice->venduti > maxVenduti){
maxVenduti = radice->venduti;
prodottoPiuVenduto = radice;
}
trovaArticoloPiuVenduto(radice->right);
}
}

ho fatto una visita dell'albero e se il nodo visitato ha campo venduti > di maxVenduti salvo il nodo nella variabile globale prodottoPiuVenduto di tipo struct prodotto *.
In questo modo però sia la variabile maxVenduti sia la variabile prodottoPiuVenduto sono globali. Mi chiedevo se c'era un modo per effettuare il confronto..e solo al termine della visita di tutto l'albero restituire il nodo con campo venduti più grande.
Cerco di spiegarmi meglio: poniamo che 3 nodi vengano visitati, nel primo il campo venduti sia = a 1, nel secondo 2 e nel terzo 3. In tutti e tre i casi, il confronto avrà esito positivo e la variabile prodottoPiuVenduto punterà prima al nodo1, poi al nodo2 e infine al nodo3. Alla fine la variabile prodottoPiuVenduto punterà giustamente al nodo3, ma mi sembrano un po' inutili i due assegnamenti precedenti.
Non so se sono stato molto chiaro..ma spero mi abbiate capito.

Draganbao

[{Bl4d3}]

vabbè... ma dato che l'albero non è ordinato rispetto ai pezzi venduti devi per forza visitarlo tutto per essere sicuro di trovare il massimo.

Quindi l'unico modo per trovarlo è proprio questo, un massimo provvisorio che aggiorni man mano, ci sta poco da fare. Volendo puoi evitare le variabili globali, ma per il problema degli assegnamenti non si può far niente.

[draganbao]

Mi faresti vedere come modifichi la funzione mettendo le variabili locali invece che globali... io non riesco.
Ti ringrazio

[{Bl4d3}]

struct prodotto *trovamax(struct prodotto *radice)
{
  if (radice == NULL)
    return NULL;
  else
  {
    struct prodotto *max = radice;
    struct prodotto *maxl = trovamax(radice->left);
    struct prodotto *maxr = trovamax(radice->right);
    if (maxr != NULL)
      if (max->venduti < maxr->venduti)
        max = maxr;
    if (maxl != NULL)
      if (max->venduti < maxl->venduti)
        max = maxl;
    return max;
  }
}

Non l'ho provata, ma dovrebbe funzionare, fammi sapere...

[draganbao]

Si, funziona benissimo, grazie mille.

Praticamente scendi prima nel sottoalbero sinistro, e poi in quello destro...e risalendo effettui i confronti e se il confronto ha esito positivo ritorni il max?

[{Bl4d3}]

imposto come massimo provvisorio la radice, poi trovo il massimo del sottoalbero sinistro, il massimo del sottoalbero destro.

Se esistono (non sono NULL) e sono maggiori del massimo provvisorio, allora lo aggiorno e alla fine lo ritorno...