[C] aiuto: alberi binari

[vlr]

Salve gente!

Ho un normalissimo, banalissimo, schifosissimo albero binario con puntatori, il problema è questo: mi serve un algoritmo che mi visualizzi i nodi di un particolare livello (se ce ne sono)... stavo provando a modificare la visita Levelorder ma non ho combinato nulla di utile.
Qualche anima pia presta soccorso?

[anx721]

Ti propongo un algoritmo ricorsivo, che è piu semplice, l'ideà è di passare come argomento il valore che rappresenta il livello corrente (currentLevel), oltre al valore che rappresenta il livello da stampare (level); il livello inizio a contarlo dalla radice, cioè la radice ha livello zero; figli della radice hanno livello 1, ecc ecc... Se inizi a contare il livello dalle foglie, l'algoritmo è diverso:

void printLevel(tree T, int currentLevel, int level){
    if(T == NULL)
        return;

    if(curentLevel == level){
         printf("%d\n", T -> elem);
         //Se questo nodo è a livello level non c'è bisogno di
         //richiamare la procedura sui figli che saranno a
         //livello magiore
         return;
    }
    printLevel(T -> left, currentLevel + 1, level);
    printLevel(T -> right, currentLevel + 1, level);
}

[vlr]

Originariamente inviato da anx721
Ti propongo un algoritmo ricorsivo, che è piu semplice, l'ideà è di passare come argomento il valore che rappresenta il livello corrente (currentLevel), oltre al valore che rappresenta il livello da stampare (level); il livello inizio a contarlo dalla radice, cioè la radice ha livello zero; figli della radice hanno livello 1, ecc ecc... Se inizi a contare il livello dalle foglie, l'algoritmo è diverso:

void printLevel(tree T, int currentLevel, int level){
    if(T == NULL)
        return;

    if(curentLevel == level){
         printf("%d\n", T -> elem);
         //Se questo nodo è a livello level non c'è bisogno di
         //richiamare la procedura sui figli che saranno a
         //livello magiore
         return;
    }
    printLevel(T -> left, currentLevel + 1, level);
    printLevel(T -> right, currentLevel + 1, level);
}

TI VOGLIO BENE!!!

Facciamo un ultimo piccolo sforzo?
La complessità sarebbe pari ai nodi di quel livello ma come la scrivo?
T(n) = b + 2T(n-1)
dove b è la stampa del nodo attuale e 2T(n-1) le successive chiamate... però non mi suona bene... :master:

In ogni caso grazie!

[}gu|do[z]{®©]

già che siamo in topic [alberi binari ]

anx.. tu che sei il mio profeta... avresti già pronta una funzioncina che elimina un elemento qualsiasi [passato come parametro] da un albero di ricerca? Se ne hai una ricorsiva ed una iterativa è il top...

danke

[Shores]

In un albero binario completo, ovvero in cui non manca mai nessun figlio fino alle foglie, i nodi di livello N sono semplicemente 2 elevato alla N.

Questo però non vuol dire che un algoritmo che li raggiunga sia di complessità di 2 elevato alla N, poichè esso è comunque costretto a visitare tutto l'albero sovrastante.

Quindi, nel caso peggiore, la complessità è pari alla somma per K che va da N a zero di 2 elevato K, ovvero pari a (2 elevato alla N+1) - 1.

Tralaltro l'algoritmo proposto da anx721 è inutilmente pesante, poichè procede nell'analisi di TUTTO l'albero anche quando il livello richiesto è stato superato; sarebbe stato più giusto attivare la ricorsione SOLO se il livello attuale era MINORE di quello cercato.

Infatti, i figli di un nodo di livello J non potranno che avere livello J+1; ciò implica che se ho trovato un nodo del livello cercato i suoi figli (e i suoi nipoti e così via) saranno di certo ignorabili poichè aventi livelli di certo superiori.

[vlr]

Originariamente inviato da Shores
In un albero binario completo, ovvero in cui non manca mai nessun figlio fino alle foglie, i nodi di livello N sono semplicemente 2 elevato alla N.

Questo però non vuol dire che un algoritmo che li raggiunga sia di complessità di 2 elevato alla N, poichè esso è comunque costretto a visitare tutto l'albero sovrastante.

Quindi, nel caso peggiore, la complessità è pari alla somma per K che va da N a zero di 2 elevato K, ovvero pari a (2 elevato alla N+1) - 1.

Quindi sarebbe meglio, in questo caso, scegliere l'implementazione tramite array che accederebbe immediatamente alla posizione più a sinistra del livello e visiterebbe solo i nodi di quel livello?

Tralaltro l'algoritmo proposto da anx721 è inutilmente pesante, poichè procede nell'analisi di TUTTO l'albero anche quando il livello richiesto è stato superato; sarebbe stato più giusto attivare la ricorsione SOLO se il livello attuale era MINORE di quello cercato.

Infatti, i figli di un nodo di livello J non potranno che avere livello J+1; ciò implica che se ho trovato un nodo del livello cercato i suoi figli (e i suoi nipoti e così via) saranno di certo ignorabili poichè aventi livelli di certo superiori.

Non vorrei abusare... ma tu come lo modificheresti? E la complessità come diventerebbe?

In ogni caso grazie!

[anx721]

Originariamente inviato da Shores

Tra l'algoritmo proposto da anx721 è inutilmente pesante, poichè procede nell'analisi di TUTTO l'albero anche quando il livello richiesto è stato superato; sarebbe stato più giusto attivare la ricorsione SOLO se il livello attuale era MINORE di quello cercato.

Infatti, i figli di un nodo di livello J non potranno che avere livello J+1; ciò implica che se ho trovato un nodo del livello cercato i suoi figli (e i suoi nipoti e così via) saranno di certo ignorabili poichè aventi livelli di certo superiori.

Infatti se leggi bene il mio algoritmo, corredato di commenti, c'è scritto:

    if(curentLevel == level){
         printf("%d\n", T -> elem);
         //Se questo nodo è a livello level non c'è bisogno di
         //richiamare la procedura sui figli che saranno a
         //livello magiore
         return;
    }
    printLevel(T -> left, currentLevel + 1, level);
    printLevel(T -> right, currentLevel + 1, level);

da cui si vede che quando si raggiunge il livello k desiderato si stampa il nodo e poi c'è return cosicchè le chiamate ricorsive non vengono eseguite sui nodi a livello maggiore :quote:

La complessita è ovviamente lineare rispetto al numero dei nodi (nel caso peggiore infatti k è pari all'altezza dell'albero quindi bisogna visitare tutti i nodi); come impostare le equazioni di ricorrenza ora non mi ricordo.



PS x }gu|do[z]{®©: poi vedo

[Shores]

Si, se l'albero è completo, ovvero se tutti i nodi di ogni livello esistono, allora di sicuro l'implementazione ad array renderebbe 2 elevato N la complessità dell'algoritmo, ovvero lo renderebbe lineare sul numero di elementi restituiti.

A proposito dell'algoritmo di anx721, chiedo venia: effettivamente il return c'è, e quindi il tutto smette di visitare i figli non necessari, certo è che se fosse stato scritto come un if / else sarebbe stato di lettura MOLTO più chiara.

Altrettanto, l'algoritmo di anx721 non è certo lineare rispetto ai nodi risultato, visto che percorre tutti i nodi dell'albero fino a quelli del livello richiesto.

Ciao!

[vlr]

Un grosso grazie a tutti coloro che mi hanno aiutato, esame superato!