Informatyka MIMUW

Ćwiczenia na drzewa z elementami procedur wyższych rzędów:

1. Dane są: definicja typu tree i procedura fold_tree:

    
         type 'a tree =  Node of 'a * 'a tree list;;
    
         let rec fold_tree f (Node (x, l)) = 
           f x (map (fold_tree f) l);;
    

   Użyj procedury fold_tree do zaimplementowania:

   1. policzenia liczby węzłów w drzewie,
   2. sprawdzić czy drzewo jest zrównoważone, tzn. wszystkie jego liście są na tej samej głębokości,
   3. sprawdzić czy drzewo regularne, tzn. wszystkie jego wierzchołki, z wyjątkiem liści, są tego samego stopnia,
   4. procedury preorder/postorder : 'a tree -> 'a list, która przekształca dane drzewo w listę jego elementów w porządku pre-order/post-order (zwróć uwagę na efektywność).
2. Dane są: definicja typu bin_tree i procedura fold_bin_tree:

    
           type 'a bin_tree = Node of 'a bin_tree * 'a * 'a bin_tree | Null;;
           let rec fold_bin_tree f a t = 
             match t with
               Null -> a |
               Node (l, x, r) -> f x (fold_bin_tree f a l) (fold_bin_tree f a r);;
    

   Użyj procedury fold_bin_tree do zaimplementowania:

   1. policzenia liczby węzłów w drzewie,
   2. policzenia wysokości drzewa,
   3. policzenia średnicy drzewa,
   4. sprawdzenia czy drzewo jest drzewem BST (dla drzewa liczb zmiennopozycyjnych, tzn. typu float tree),
   5. sprawdzenia, czy drzewo ma kształ drzewa AVL (tzn., czy dla każdego węzła drzewa wysokości jego obu poddrzew różnią się o co najwyżej 1),
   6. zaimplementowania procedury map_bin_tree -- odpowiednika procedury map_tree dla drzew binarnych,
   7. skonstruowania listy elementów znajdujących się w wierzchołkach drzewa, w kolejności infiksowej,
   8. procedury \(\mathtt{path}: \alpha\ \mathtt{tree} \to \alpha\ \mathtt{list}\), która znajduje najdłuższą ścieżkę (jedną z) od korzenia do liścia i zwraca listę wartości znajdujących się w węzłach tworzących tę ścieżkę, w kolejności od korzenia do liścia.
   9. zaimplementowania procedury \(\mathtt{levels} : \alpha\ \mathtt{tree} \to \alpha\ \mathtt{list~list}\),
      która dla danego drzewa zwraca listę list węzłów drzewa znajdujących się na kolejnych poziomach głębokości.
      Listy składowe powinny być podane w kolejności od korzenia w głąb drzewa.
      Wartości z węzłów znajdujących się na tej samej głębokości powinny być uporządkowane od lewej do prawej.
3. Zadeklaruj typ danych reprezentujący abstrakcyjną składnię wyrażeń arytmetycznych.
   Napisz procedurę obliczającą wartość wyrażenia.
   
   Rozszerz składnię wyrażeń o zmienne.
   Procedura obliczająca wartość wyrażenia będzie wymagać dodatkowego parametru --- wartościowania
   zmiennych, czyli funkcji, która nazwie zmiennej przyporządkowuje jej wartość.