IALweb Homepage
Forum Home Forum Home > Programmazione > Programmazione > C/C++ - VISUAL C++
  New Posts New Posts RSS Feed - Distanza minima radice-foglia
  FAQ FAQ  Forum Search   Events   Register Register  Login Login


REGISTRATEVI su IALWeb forum!

Distanza minima radice-foglia

 Post Reply Post Reply
Author
Message
salvogsm80 View Drop Down
Nuovo Utente
Nuovo Utente


Joined: 17/Gen/2013
Status: Offline
Points: 4
Post Options Post Options   Thanks (0) Thanks(0)   Quote salvogsm80 Quote  Post ReplyReply Direct Link To This Post Topic: Distanza minima radice-foglia
    Posted: 17/Gen/2013 at 09:54
Ciao a tutti,
dovrei scrivere un programmino in c che mi calcoli la minima distanza tra la radice di un albero binario di ricerca e una foglia.Come posso implementare il tutto?
Grazie mille
Back to Top
Sponsored Links


Back to Top
willy55 View Drop Down
Moderatore
Moderatore
Avatar
Esperto di Access

Joined: 03/Ago/2011
Location: Italy
Status: Offline
Points: 10254
Post Options Post Options   Thanks (0) Thanks(0)   Quote willy55 Quote  Post ReplyReply Direct Link To This Post Posted: 17/Gen/2013 at 22:02
Per affrontare quanto ti proponi (calcolo della minima distanza tra radice e foglia di un albero binario) ti consiglio (per prima cosa) di acquisire una padronanza teorica e poi affrontare l'aspetto realizzativo,
I seguenti link possono fornirti uno spunto da cui partire:
http://www.iro.umontreal.ca/~vaucher/Publications/Vaucher_BST3.pdf
http://epaperpress.com/sortsearch/download/sortsearch.pdf
http://esercizicpp.sourceforge.net/
http://math.hws.edu/eck/cs225/s03/binary_trees/
Willy
Back to Top
salvogsm80 View Drop Down
Nuovo Utente
Nuovo Utente


Joined: 17/Gen/2013
Status: Offline
Points: 4
Post Options Post Options   Thanks (0) Thanks(0)   Quote salvogsm80 Quote  Post ReplyReply Direct Link To This Post Posted: 17/Gen/2013 at 22:33
Grazie Willy
ma a me serviva solo qualche idea su come svolgere questo esercizio!
Grazie ancora
Ciao
Back to Top
willy55 View Drop Down
Moderatore
Moderatore
Avatar
Esperto di Access

Joined: 03/Ago/2011
Location: Italy
Status: Offline
Points: 10254
Post Options Post Options   Thanks (0) Thanks(0)   Quote willy55 Quote  Post ReplyReply Direct Link To This Post Posted: 18/Gen/2013 at 18:58
Visto che chiedi qualche idea su come svolgere questo esercizio dovrai realizzare funzioni ricorsive in grado di:
- percorrere l'albero (in base ad un ordine di visita previsto);
- tenere traccia attraverso un contatore del numero dei nodi visitati (nel sotto-albero) in modo da calcolare la profonditÓ;
- procedere sino ad individuare la foglia ricercata;
- determinare la minima distanza fra root e foglia in base al percorso.
Willy
Back to Top
salvogsm80 View Drop Down
Nuovo Utente
Nuovo Utente


Joined: 17/Gen/2013
Status: Offline
Points: 4
Post Options Post Options   Thanks (0) Thanks(0)   Quote salvogsm80 Quote  Post ReplyReply Direct Link To This Post Posted: 22/Gen/2013 at 10:22
Grazie mille sei stato molto gentile!
Back to Top
salvogsm80 View Drop Down
Nuovo Utente
Nuovo Utente


Joined: 17/Gen/2013
Status: Offline
Points: 4
Post Options Post Options   Thanks (0) Thanks(0)   Quote salvogsm80 Quote  Post ReplyReply Direct Link To This Post Posted: 23/Gen/2013 at 21:13
Ho provato a svolgerlo in questo modo:

int DiffLevel(struct node * t)
    {
    int max_leaf = max_level(t);
    int min_leaf = level_first_leaf(t);
    return max_leaf - min_leaf;
    }
    
    int level_first_leaf(struct node * t)
    {
    if(t) {
    if(!t->sx && !t->dx) return 1; // se Ŕ una foglia restituisce 1
    else if(!t->sx) return 1 + level_first_leaf(t->dx); // altrimenti nel caso ci sia un solo ramo restituisce 1 + il valore per quel ramo
    else if(!t->dx) return 1 + level_first_leaf(t->sx);
    int val_sx = level_first_leaf(t->sx); // quando ci sono entrambi i rami
    int val_dx = level_first_leaf(t->dx);
    return 1 + ( val_sx < val_dx ? val_sx : val_dx ); // restituisce il valore minore del conteggio
    }
    return 0; // va qui solo quando l'albero Ŕ vuoto.
    }
    
    int max_level(struct node * t) {
    if(t) {
    int val_sx = max_level(t->sx);
    int val_dx = max_level(t->dx);
    return 1 + ( val_sx > val_dx ? val_sx : val_dx ); // restituisce il livello massimo per ogni ramo dell'albero
    }
    return 0;
    }


Edited by salvogsm80 - 23/Gen/2013 at 21:16
Back to Top
 Post Reply Post Reply
  Share Topic   

Forum Jump Forum Permissions View Drop Down

Forum Software by Web Wiz Forums® version 10.17
Copyright ©2001-2013 Web Wiz Ltd.

This page was generated in 0,063 seconds.