[C]Problema con alberi binari

[kily_2001]

ciao a tutti, mi dareste una mano con questo esercizio?

"Scrivere una funzione che, dato in input un albero binario, inserisca come figli sinistro e destro di
ciascuna foglia x dell'albero rispettivamente il minimo e il massimo tra tutti i nodi nel cammino
dalla radice alla foglia x."

naturalmente non voglio il codice, mi basterebbe una dritta su come affrontarlo!

grazie!!!

[kily_2001]

up!

un aiutino??

[Ifrit]

vabè sembra ovvio, programmazione ricordiva

crea una funzione che testi il valore nuovo con quello del puntatore root,
del tipo

void funzione(struct elem *nuova_strut, struct elem *root)

quindi una volta che hai testato la info contenuta nel root e quella nellanuova struttura puoi decidere se posizionare a destra o sinistra la nuova struttura, e quindi puoi avere sostanzialmente 2 casi [4 per l'esatezza, ma generalizziamo]

supponiamo che la nuova struttura deve essre posizionata a destra e che la struttura sia di questo genere:

struct elem
 {
   int info;
   struct elem *sinistra, *destra;
 } 

[list=1][*] root->destra e' uguale a NULL
assegni semplicemente
root->destra=nuova_strut
[*] root->destra e' diverso da NULL
richiami la stessa funzione in questo modo:
funzione(*nuova_strut,*root->destra)[/list=1]

Nota:
In caso la struttura la vuoi creare direttamente nella funzione madre
puoi seguire sempre questo discorso creando una funzione ausiliaria
che ti permette di fare queto gioco.
Ricoda di mettere a NULL *sinistra e *destra della nuova struttura,
altrimenti so casini :stordita:

_______________________________________

Spero di esserti stato utile, buon lavoro

[kily_2001]

come prima cosa grazie per la risposta


ok il ragionamento per l'inserimento l'ho capito ma come tengo traccia dei vari cammini radice-foglia?
i valori da inserire non li conosco a priori, dovrei in qualche modo tenere traccia del cammino e poi estrarre max e min e inserirli come figlio sx e dx alla foglia, o sbaglio?

[Ifrit]

allora, forse non ho capito il problema.....

a te serve una funzione che fornito un dato numericc deve caricarlo in una lista ad albero in mo che su ogni incrocio si possa prendere 2 strade, e queste contengono rispettivamente una numeri solo minori, l'altra numeri solo maggiori del numero contenuto nella struttura presa in considerazione in quel momento.........

tpo questo:


ora a te non interessa tener conto della strada percorsa se devi inserire un nuovo elemento....

se devi cercare il max e il min la cosa e fatta, il massimo devi andare sempre a destra finche non trovi la struttura che possiede il puntatore destra uguale a NULL, stessa cosa per il minimo verso sinistra....

poi se devi fare una lettura da min a max [o viceversa] di tutti gli elementi del tree basta rifare un discorso simile a quello di prima con la programmazione ricorsiva....

in qualunque caso non bisogna tener conto del percorso fatto.... al massimo basta tenr conto dell'elemento precedente.....

ho centrato il discorso devo spiegare meglio?

[kily_2001]

credo che la tua soluzione valga solo per un albero binario di ricerca!

se un albero non ha quelle caratteristiche il discorso non vale e devo salvarmi tutto il cammino (di ogni percorso radice-foglia)!

[Ifrit]

scusami ma un albero deve necessareamente avere delle caratteristiche di info, ed e su quello che bisogna ragionare....

fammi un esempio incui il mio discorso non trova posto perchè non riesco a immaginarmelo :master:

[kily_2001]

in pratica la funzione riceve un albero binario, e deve aggiungere ad ogni foglia dell'albero il minimo del suo cammino radice foglia come figlio sx e il massimo come figlio dx.

avendo l'albero:



devo aggiungere alla foglia "90" come figlio sx "20" e come figlio dx "90", ossia il massimoe il minimo incontrati nel cammino radice-foglia "90".

Allo stesso modo aggiungero alla foglia "35" gli elementi "20" e "80"
alla foglia "25" gli elementi "15" e "80"
alla foglia "30" gli elementi "40" e "50"
alla foglia "85" gli elementi "40" e "85"

[Ifrit]

in pratica la funzione riceve un albero binario, e deve aggiungere ad ogni foglia dell'albero il minimo del suo cammino radice foglia come figlio sx e il massimo come figlio dx.

eeeeeeeeeeh?

ma scusami, l'albero di ingresso non dovrebbe essere ordinato??? quello che hai postato non e affatto ordinato

[kily_2001]

per ordinato intendi che ogni sottoalbero sinistro di un nodo deve contenere valori minori di quel nodo e ogni sottoalbero destro deve contenere invece valori maggiori (albero binario di ricerca)?


nel testo dell'esercizio non è specificato se l'albero passato in input sia ordinato o no!