Salve ragazzi! Spero sia la sezione giusta in cui scrivere.
Ho appena fatto un compitino di dati e algoritmi, con questo esercizio all'interno:
"Scrivere una funzione ricorsiva che, passato come parametro un albero binario T, verifichi se è triangolare. Usare solo variabili locali d'appoggio, no array o altre strutture. Non si può modificare l'albero. L'interfaccia albero binario ha come metodi: root(), isEmpty(), hasLeft(), left(), hasRight(), right()" (quindi niente riguardante l'altezza dell'albero, il numero di nodi ecc ecc).
Come fare?
Cercando un po' su internet non ho trovato una effettiva definizione di albero triangolare, ma comunque è semplice: è un albero binario con tutti i livelli completi, quindi i suoi nodi sono in numero una potenza di 2 meno 1, e l'ultimo livello L dell'albero contiene 2^L nodi esterni.
Essendo ricorsiva ho pensato di visitare l'albero, e conteggiare un "+1" se la ricorsione scende a sinistra, e "-1" se scende a destra, se finita la ricorsione il conteggio è a 0 allora risulta triangolare, cioè in questa maniera:
ma sfortunatamente non basta, perché in questo caso verifica semplicemente se i nodi aventi figli ne hanno esattamente 2...!! Ovvero così:
Qualche consiglio su come farlo?
Rispondi quotando
