Ćwiczenie programistyczne na drzewa i inne struktury danych:
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.
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.
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.potnij p t powinno zwrócić listę tych drzew (w dowolnej kolejności).
rozcięcie, która znajduje taką krawędź w danym drzewie binarnym, że po jej usunięciu drzewotype tree = Node of tree * int * tree | Null;;
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).
type 'a tree =
Node of 'a * 'a tree * 'a tree |
Null;;
Skosokość drzewa jest zdefiniowana w następujący sposób:
Null wynosi 0, 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.
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:
Jak zapewnić, aby szef firmy był na przyjęciu?
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.
Rozwiązania
type 'a drzewo = Node of 'a * 'a drzewo * 'a drzewo | Null
Napisz procedurę polowa:'a drzewo -> 'a drzewo, która znajduje w zadanym drzewie taki węzeł (Node), który jest przodkiem jak najmniejszej liczby liści, ale przynajmniej połowy wszystkich liści drzewa.
type tree =
Node of int * tree * tree |
Leaf;;
Napisz procedurę \(\mathtt{odchudzanie}: \mathtt{tree} \to \mathtt{tree}\), która mając dane drzewo binarne, zwraca drzewo powstałe przez usunięcie z niego takich poddrzew
(zastępując Node(...) przez Leaf) aby suma elementów w powstałym drzewie była jak największa.
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?
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.
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.
type α tree = Node of α * α tree list;;
Ścieżkę w drzewie nazwiemy rosnącą, jeżeli wartości w węzłach na tej ścieżce, w kierunku od korzenia w dół, są rosnące.
Napisz procedurę rosnaca: int tree → int list, która znajdzie w danym drzewie najdłuższą ścieżkę rosnącą i zwróci wartości znajdujące się na niej (w kolejności od korzenia w dół). (Uwaga: szukana ścieżka nie musi zaczynać się w korzeniu i nie musi kończyć się w liściu.)
Rozwiązania
type α tree = Node of α * α tree list;;
Napisz procedurę nieparzyste: α tree → int, która dla danego drzewa policzy ile jest w nim poddrzew zawierających nieparzystą liczbę wierzchołków.
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.