Domanda Larghezza Alberi in C

Stato
Discussione chiusa ad ulteriori risposte.

Albymaster

Utente Emerald
18 Giugno 2010
719
171
94
497
Salve a tutti, da qualche giorno, nello svolgimento di un'esercizio di algoritmi e strutture dati mi sono imbattuto in un problema che non riesco a risolvere. Mi è stato dato come lavoro quello di creare un piccolo algoritmo in C in cui bisogna calcolare la larghezza di un albero e la funzione deve ritornare il puntatore al nodo con il maggior numero di figli. Premetto che ho trovato molti esempi online ma non mi sono stati d'aiuto poiché trattavano sempre Alberi Binari e quindi utilizzavano le funzioni "figlio destro" e "figlio sinistro". Ora,non sto chiedendo che mi venga già fornito l'algoritmo ma se qualcuno riuscisse a darmi uno spunto di come risolvere questo esercizio glie ne sarei molto grato. Per quanto riguarda gli alberi/code/pile etc.. Il nostro prof ci perfette di utilizzare delle funzioni già fatte come se fossero in libreria(es : creaalbero,radice,padre...etc).
Grazie :)
 
L'implementazione classica degli alberi è la left-child right-sibling, dove ogni nodo ha un puntatore al suo primo figlio (left child) e un puntatore al suo fratello più prossimo (right sibling).
C:
typedef int type;
struct Tree
{
    struct Tree *lchild, *rsibling;
    type data;
};


Se vuoi trovare la larghezza dell'albero puoi effettuare un breadth-first search (visita level-order) dove sostanzialmente ad ogni chiamata ricorsiva conti il numero di nodi che hai alla tua destra: se ho un fratello destro mi segno 1 e chiamo ricorsivamente, se ho un figlio chiamo ricorsivamente senza aumentare il counter della larghezza.

Se vuoi trovare il nodo con più figli puoi creare una funzione che ritorna il numero di figli di un dato nodo (un banale while) e utilizzarla in mezzo ad un qualsiasi algoritmo di visita.

Sono un pugno di righe di codice, devi solo capire bene cosa devi fare, ma in buona sostanza l'algoritmo te l'ho descritto.
 
  • Mi piace
Reazioni: Albymaster
Nuovo Esatto Beta, con larghezza massima intendo il numero maggiore di nodi in un determinato livello
Io per larghezza avevo inteso un'altra cosa, per esempio:
prova.jpg

  • la larghezza del nodo A è 1 (larghezza = 1);
  • B è immediatamente sotto ad A, quindi non allarga l'albero;
  • C è alla destra di B, quindi allarga l'albero (larghezza = 2);
  • D è immediatamente sotto a C, quindi non allarga l'albero;
  • E ed F sono alla destra di D, quindi allargano l'albero di 2 (larghezza = 4). Nota che sarebbe stata 3 se D,E,F fossero stati figli di B.

Se per larghezza intendi il massimo numero di nodi che hai su un livello, quindi quella che nell'immagine sotto è 4 (io la contavo come 6), devi procedere diversamente. Va comunque bene la visita level-order (bfs), ma le somme vanno fatto in modo diverso da come te le ho descritte.
prova.jpg



In entrambi i casi mi pare di aver capito che le funzioni che ti servono siano due: una per calcolare la larghezza e una per ricavare il nodo con più figli (figli che potrebbero essere su un livello diverso da quello di larghezza massima).
Se non ho capito bene prova a spiegarti meglio perché le soluzioni che ti avevo proposto potrebbero non andar bene.
 
No no st3ve ora hai inteso correttamente quel che cercavo di chiedere. Nella seconda immagine la larghezza che mi serve ottenere a me è 4 e il nodo che mi interessa è la radice, poichè appunto ha 4 figli.
 
Ok, allora confermo. Visita level-order classica (usando una coda) con un contatore associato ad ogni livello, se ti servono maggiori informazioni fammi sapere cosa devo spiegarti.
 
Allora il tuo non è proprio un albero "standard", essendo un albero ad al più n vie dovresti applicare algoritmi più complessi. Per esempio dovresti utilizzare una BFS (algoritmo applicato ai grafi) con le opportune modifiche per il tuo caso, visto che non conosci (?) a priori il numero n.
 
Diciamo che conosco l'algoritmo BFS ma non pensavo di poterlo usare. Nel senso che avendolo appunto studiato nei grafi io nel momento in cui avessi dovuto svolgere l'esercizio sull'albero non sarei ancora stato a conoscenza del BFS.
 
Il breadth-first search in un albero è l'equivalente della visita in level-order, il prerequisito per applicare questo algoritmo è la conoscenza delle code (queue).
 
Il breadth-first search in un albero è l'equivalente della visita in level-order, il prerequisito per applicare questo algoritmo è la conoscenza delle code (queue).
Ora lo utilizzerò, però il prof non ne aveva parlato fino a che non siamo arrivati ai grafi..Comunque ora proverò a seguire i consigli e vi farò sapere
 
Stato
Discussione chiusa ad ulteriori risposte.