Ćwiczenia 6: Struktury danych

Ćwiczenie programistyczne na drzewa i inne struktury danych:

  1. Zdefiniuj typ reprezentujący drzewa o wierzchołkach dowolnego (skończonego) stopnia.
    Zdefiniuj garść procedur operujących na takich drzewach (np. głębokość, liczbę elementów, lista elementów w porządku prefiksowym/postfiksowym).
  2. Dana jest deklaracja typu drzew binarnych:

     
         type α tree = 
           Node of α tree * α  * α tree | 
           Null;;
     

    Drzewo nazywamy ultralewicowym jeśli głębokości kolejnych liści (Null), od lewej do prawej, tworzą ciąg nierosnący.
    Napisz procedurę ultraleft : α tree → bool, która sprawdza czy dane drzewo jest ultralewicowe.

  3. [II OI, zadanie Obchodzenie drzewa skokami]
    Jak obejść wszystkie wierzchołki drzewa (ogólnego) tak, aby odległość między kolejnymi
    wierzchołkami nie przekraczała 3.
  4. Dana jest deklaracja typu drzew binarnych:

     
          type α tree = 
            Node of α tree * α * α tree | 
            Nil;;
     

    Napisz procedurę liscie : α tree → α list, która tworzy listę wartości znajdujących się w liściach (Node) drzewa.

  5. Napisz procedurę, która dla dowolnego drzewa binarnego poprawia je tak, że spełnia ono słabszą wersję warunku BST:
    dla dowolnego węzła, lewy syn nie jest większy, a prawy nie jest mniejszy, niż węzeł.
  6. Napisz funkcję potnij, która dla danego predykatu \(p\) typu \(\alpha \to \mathtt{bool}\), oraz drzewa \(t\) typu \(\mathtt{\alpha\ tree}\), zwróci następujący wynik.
    Wybierzmy wszystkie węzły drzewa \(t\) zawierające wartości, które spełniają predykat \(p\) i usuńmy z drzewa krawędzie łączące te węzły z ich rodzicami (w przypadku korzenia, nie usuwamy żadnej krawędzi).
    W rezultacie drzewo \(t\) może się rozpaść na pewną liczbę mniejszych drzew.
    potnij p t powinno zwrócić listę tych drzew (w dowolnej kolejności).
  7. Napisz procedurę rozcięcie, która znajduje taką krawędź w danym drzewie binarnym, że po jej usunięciu drzewo
    rozpada się na dwa drzewa o minimalnej różnicy liczb węzłów.
    (Wynikiem procedury powinien być dolny koniec szukanej krawędzi.)
  8. [PCh]
    Dana jest deklaracja typu drzew binarnych:
    type tree = Node of tree * int * tree | Null;;
    Napisz procedurę \(\mathtt{symetryczne} : \mathtt{tree} \to \mathtt{bool}\), która sprawdza, czy drzewo jest symetryczne (ze względu na odbicie lewo-prawo).
  9. Dana jest deklaracja typu reprezentującego wyrażenia logiczne:

     
          type expr = 
            And of expr * expr |
            Or of expr * expr |
            Not of expr | 
            Value of bool;;
     

    Warianty And, Or i Not reprezentują odpowiednie operacje logiczne,
    natomiast wariant Value reprezentuje wartość logiczną true lub false.

    Napisz funkcję wartościowania : expr → int,
    która dla danego wyrażenia policzy na ile różnych sposobów można przypisać wszystkim
    wariantom Value wartości logiczne, tak aby wartość całego wyrażenia wyliczała się do true.

    Przykład: wartościowania Or(Value true, Value false) = 3,
    gdyż wyrażenie wyliczy się do true, w trzech przypadkach:
    Or(Value true, Value true), Or(Value true, Value false), Or(Value false, Value true).

  10. Dana jest deklaracja typu drzew binarnych:

     
          type 'a tree = 
            Node of 'a * 'a tree * 'a tree | 
    	Null;;
     

    Skosokość drzewa jest zdefiniowana w następujący sposób:

    • skosokość Null wynosi 0,
    • skosokość \(\mathtt{Node}(x, t_1, t_2)\) jest równa \(\max(2 \cdot s_1, 2 \cdot s_2 + 1)\), gdzie \(s_1\) i \(s_2\) to skosokości, odpowiednio, \(t_1\) i \(t_2\).

    Dla danego drzewa wolno nam w dowolnych jego węzłach zamieniać miejscami lewe i prawe poddrzewa.
    Napisz procedurę \(\mathtt{skosokosc}: \alpha\ \mathtt{tree} \to \alpha\ \mathtt{tree}\), która przekształca dane drzewo tak, aby zminimalizować jego skosokość.
    Na przykład, dla:

     
          t = Node(5,
                Node(4, Null, Node(2, Null, Null)), 
                Node(6, 
                  Node(1, Null, Null), 
                  Node(3, Null, Null)
                )
              )
     
          skosokosc t = Node(5,
                          Node(6, 
                            Node(1, Null, Null), 
                            Node(3, Null, Null)
                          ),
                          Node(4, Node(2, Null, Null), Null) 
                        )
     

    Skosokość tak uzyskanego drzewa wynosi 6.

  11. [CLR, ćw. 16-4]
    Firma planuje zorganizować przyjęcie. Hierarchia stanowisk w firmie ma strukturę drzewa (ogólnego):

     
          type tree = Node of (int * tree list);;
     

    Każdy pracownik charakteryzuje się pewną "towarzyskością" wyrażoną liczbą dodatnią.
    Napisz program, który dobierze gości tak, aby:

    • na przyjęciu nie był obecny bezpośredni przełożony żadnego z gości,
    • suma współczynników towarzyskości gości była maksymalna.

    Jak zapewnić, aby szef firmy był na przyjęciu?

  12. Dane jest definicja typu:

     
          type tree = 
            Node of tree * tree | 
    	Null
     

    .
    Odległością między dwoma wierzchołkami (Node) w drzewie nazywamy minimalną
    liczbę krawędzi jakie trzeba przejść z jednego wierzchołka do drugiego.
    Średnicą drzewa nazwiemy maksymalną odległość między dwoma węzłami (Node) w drzewie.
    Przyjmujemy, że średnica pustego drzewa (Null) jest równa 0.

    Napisz procedurę średnica : tree → int, która oblicza średnicę danego drzewa.

  13. Dana jest deklaracja typu:

     
          type  drzewo =
            Node of α * α drzewo * α drzewo |
            Null 
     

    Napisz procedurę środek : α drzewo → α drzewo, która znajduje w zadanym drzewie taki
    węzeł (Node), dla którego maksymalna spośród jego odległości od liści jest jak najmniejsza.
    Wynikiem tej procedury powinno być poddrzewo zakorzenione w wyznaczonym węźle.

    Co się zmieni, jeżeli będziemy chcieli znaleźć wierzchołek, dla którego
    minimalna spośród jego odległości do liścii jest jak największa?

  14. Dana jest deklaracja typu drzew binarnych, w których węzłach znajdują się liczby całkowite:

     
          type tree = 
            Node of int * tree * tree |
            Null 
     

    Przekrojem drzewa nazwiemy dowolny taki zbiór jego wierzchołków (Node), że na każdej ścieżce
    od korzenia do liścia (Null) znajduje się dokładnie jeden wierzchołek należący do przekroju.

    Napisz procedurę cut : tree → int, która dla danego drzewa wyznaczy najmniejszą możliwą sumę liczb
    znajdujących się w wierzchołkach tworzących przekrój danego drzewa.

  15. Rozważmy drzewo binarne, w którego wierzchołkach pamiętane są różne dodatnie liczby całkowite.
    Dane są dwie listy: wyniki obejścia drzewa w porządku infiksowym i prefiksowym.
    Napisz procedurę, która odtwarza drzewo na podstawie takich dwóch list.
  16. Napisz procedurę, która przekształca dane drzewo binarne w wyważone drzewo binarne, zachowując kolejność elementów w porządku infiksowym.
  17. Dana jest definicja typu drzew dowolnego stopnia:

              type α tree = Node of α * α tree list;;
     

    Napisz procedurę \(\mathtt{liscie} : \alpha\ \mathtt{tree} \to \mathtt{int~list}\), która dla danego drzewa liczy ile w tym drzewie jest liści na poszczególnych głębokościach i zwraca listę liczb postaci \([g_0; g_1; \dots; g_h]\), gdzie \(g_i\) to liczba liści znajdujących się na głębokości \(i\), a \(h\) to wysokość drzewa.

  18. Dana jest deklaracja typu drzew binarnych:

     
          type tree = Node of tree * int * tree | Null;;
     

    Napisz procedurę czapeczka : tree → tree → int, która obliczy na ilu poziomach, idąc od góry,
    dane drzewa są identyczne, tzn. na tych poziomach drzewa mają ten sam kształt, a w odpowiadających sobie wierzchołkach są takie same liczby.

  19. Dany jest typ reprezentujący drzewa binarne:

     
          type α tree = 
            Node of α tree * α  *  α tree |
            Null;;
     

    Zdefiniuj typ α przechadzka oraz procedury:

     
          make    : α tree  → α walk
          goleft    : α walk → α walk
          goright  : α walk → α walk
          goup     : α walk → α walk
          lookup   : α walk → α tree
     

    umożliwiające ,,przechadzanie'' się po drzewie i oglądanie go.
    Wywołanie make d powinno konstruować przechadzkę, w której znajdujemy się w korzeniu drzewa d.
    Wywołanie goleft p powinno konstruować przechadzkę powstałą przez przejście do lewego poddrzewa.
    Analogicznie powinny działać procedury goright i goup.
    Procedura ookup powinna zwrócić poddrzewo zaczepione w wierzchołku drzewa, w którym aktualnie jesteśmy.

    Podczas przechadzki po drzewie możemy przebywać jedynie w wierzchołkach Drzewo _.
    Jeśli nastąpi próba wejścia do liścia Lisc lub wyjścia ,,ponad'' korzeń, należy podnieść wyjątek Poza_drzewem.