Riporto qui un classico dell’informatica di base: la realizzazione di un albero binario per l’ordinamento.
Quello dell’albero binario è un algoritmo che consente di ordinare dei valori in base al criterio di inserimento e successivamente di lettura.
Per far capire meglio il procedimento vediamo anzitutto come funziona.
Immaginiamo di avere la sequenza di numeri 3, 4, 1, 7, 6, 5, 8, 11, 9. L’algoritmo prevede la creazione di una struttura ad albero, composta di nodi, dove ogni nodo contiene un valore e un ramo di sinistra e uno di destra, che puntano rispettivamente al valore minore e maggiore, rispetto al valore nel nodo. La creazione dell’albero procederà quindi come nel video soprastante.
La lettura avverrà invece a partire dal primo nodo, procedendo anzitutto sul nodo di sinistra, poi stampando il valore del nodo corrente e poi procedendo sul nodo di destra. Come illustrato nella seguente animazione:
Procedendo in questo modo otterremo tutti i valori ordinati.
Questo algoritmo può essere scritto in Python nel modo seguente:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 |
class Nodo: def __init__(s,v = None): s.valore = v s.sx = s.dx = None def aggiungi(nodo,v): if nodo.valore is None: nodo.valore = v nodo.sx = Nodo() nodo.dx = Nodo() elif v < nodo.valore: aggiungi(nodo.sx,v) else: aggiungi(nodo.dx,v) def stampa(nodo): if nodo.valore is not None: stampa(nodo.sx) print(nodo.valore) stampa(nodo.dx) radice = Nodo() numeri = [3,2,7,4,6,5,9,10] for n in numeri: aggiungi(radice,n) stampa(radice) |