Newsgroup: it.comp.lang.c++
Titolo: algoritmo aiuto

chi sa dirmi come deve essere fatto un algoritmo che riceva un albero
binario e calcoli di quanti livelli è composto?
e quello per contare da quanti nodi foglia è composto l'albero?
un grazie a tutti

 e quello per contare da quanti nodi foglia è composto l'albero?
Lo esplori ricorsivamente (è semplice negli alberi binari) e ti memorizzi 
i dati man mano che passi tra i nodi foglia.
-- 
Luc.


ho provato con questa funzione però non mi fa niente
int conta (TREENODEPTR treeptr)                            a treeptr ho
assegnato rootptr che è il primo
{
nodo dell'albero
int a=0;
while(treeptr!=NULL){
treeptr = treeptr->leftptr;
if(treeptr->leftptr=NULL)
treeptr = treeptr->rightptr;
a++;}
return a;
}
si accettano suggerimenti.

 si accettano suggerimenti.
La funzione che hai scritto č sbagliata.
Immagina la situazione seguente:
                       O
                      / \
                     O  O
                    / \  \
                   O  O   O
La tua funzione dovrebbe (e dico dovrebbe xchč non l'ho
fatta girare, se non a mente) ritornare 4, perchč il
sottoalbero sinistro non viene esaminato, visto che tu fai il
ciclo usando come nuovo puntatore l'ultimo non NULL.
Secondo me, l'errore sta nel come tu pensi l'albero binario,
che ti pensa a esplorarlo secondo algoritmi iterativi, mentre
sarebbe *molto* piů semplice (magari una volta fattaci
l'abitudine) pensarlo in modo ricorsivo.
Definisci l'albero cosě:
    albero binario č
    1) Un albero vuoto
    2) Un nodo con due figli
La funzione viene facilmente riscritta cosě
int contanodi(albero* alb)
{
    if (alb == 0) return 0;
    return 1 + contanodi(alb->sinistro) + contanodi(alb->destro);
}
Semplice no?
Eido

 Eido
Dimenticavo, questa funziona conta il numero di nodi di un albero e
niente piů.
Eido

"Eido" <NS_yoa...@Minfinito.it> ha scritto nel messaggio
news:Wt2f9.73492$ub2.1...@news1.tin.it...

grazie mille.
invece come faccio per contare i livelli di un albero e per visitarli alla
ricerca un elemento?

 ricerca un elemento?
Per visitarli alla ricerca di un elemento:
TREENODEPTR cerca (TREENODEPTR treeptr, int elem)
{
	if (treeptr->value == elem)
		return treeptr;
	if (treeptr->leftptr != 0) {
		TREENODEPTR p = cerca (treeptr->leftptr, elem);
		if (p != 0)
			return p;
	}
	if (treeptr->rightptr != 0) {
		TREENODEPTR p = cerca (treeptr->rightptr, elem);
		if (p != 0)
			return p;
	}
 
	return 0;
}
In pratica cerca se il valore del nodo passato č uguale al valore da 
cercare, in caso affermativo torna un puntatore al nodo, altrimenti cerca 
ricorsivamente prima nel sottoalbero sinistro e poi in quello destro. Se 
anche qui le ricerche falliscono ritorna 0.
Per il numero di livelli non saprei, purtroppo Algoritmi in C l'ho 
studiato troppo in fretta e non mi ricordo. Se trovo qualcosa che non 
faccia schifo te lo posto. Altrimenti, aspetta qualcuno che abbia qualche 
libro di algoritmi o cerca con google.
-- 
Andrea Bergia - studente
Linux Registred User #281550

 ricerca un elemento?
Contare i livelli è altrettanto semplice.
Basta osservare che il livello di un albero è uguale a 1 +
il massimo tra il livello del sottoalbero sx e sottoalbero
dx e assegnare all'albero vuoto una profondità di -1 (in
pratica un albero con un solo nodo ha livello 0)
int livello(albero* alb)
{
    if (alb == 0) return -1;
    return 1 + max(livello(alb->sx), livello(alb->dx);
}
La funzione max() ritorna, ovviamente, il max tra i due
parametri.
Eido