Résumé de section

  • Lezione 9: 16/10/25

    • Alberi: applicazioni; definizioni; terminologia.

    Lezione 10: 21/10/25

    • Alberi: applicazioni; definizioni; terminologia.
    • Dimostrazione Proposizione 8.3 del testo (esercizio R-8.2)
    • Interfacce: Iterator, Iterable e Tree
    • Calcolo della profondità di un nodo (algoritmi ricorsivo e iterativo);
    • Calcolo dell'altezza di un nodo e di un albero;
    • Proposizione 8.4 del testo.

    Lezione 11: 22/10/25

    • Visite in preorder e postorder (pseudocodici, analisi ed esempi).
    • Algoritmi AllDepths e DiskSum.
    • Alberi binari: definizione; interfaccia.
    • Alberi binari propri: definizione; relazioni tra foglie, nodi interni, nodi e altezza.

    Lezione 12: 23/10/25

    • Alberi binari propri: dimostrazione delle relazioni tra foglie, nodi interni, nodi e altezza; visita inorder.
    • Parse Tree di un'espressione.
    • Rappresentazione infissa e postfissa (polacca inversa) di una espressione e uso della rappresentazione postfissa.
    • Algoritmi infix e postfix per la generazione di una espressione a partire dal suo Parse Tree, in rappresentazione rispettivamente infissa e postfissa.

    Lezione 13: 28/10/25

    • Esercizi: calcolo altezza tramite max profondità di una foglia e algoritmo LCA (Slide 60 sugli Alberi Generali); algoritmo allLiveAncestors (Slide 61 sugli Alberi Generali); relazione tra foglie e nodi interni quando ogni nodo interno ha >= 2 figli e algoritmo preorderNext (Slide 44 sugli Alberi Binari).

    Lezione 14: 29/10/25

    • Esercizi: algoritmi heightSum, All3Balanced, e maxOnHeight (Slide 37-43, 45 e 46 sugli Alberi Binari); 
    • Cenni sulla implementazione in Java di Alberi Generali e Binari. 

    Materiale: