Metody Programowania - Lista 6

Zadanie 1

Węzły drzewa binarnego są listami czteroelemetowymi, których pierwsze pole służy jako klucz zaś ostatnie (czwarte) to wartość związana z węzłem. Napisać funkcję (5 różnych) która:

Obliczy ilość elementów drzewa
Obliczy sumę wartości węzłów (zakładając że są one liczbowe)
Obliczy wysokość drzewa (tzn. ilość poziomów, formalnie wysokość drzewa pustego to 0, zaś niepustego to 1 plus maksimum wysokości poddrzew)
Jako wartość wpisze ilość elementów poddrzewa którego korzeniem jest dany element (ta funkcja modyfikuje źródłowe drzewo)
Jako wartość wpisze wysokść poddrzewa którego korzeniem jest dany element (ta funkcja modyfikuje źródłowe drzewo)

Zadanie 2

Napisać funkcję która mając dane drzewo, takie jak w zadaniu 1 i funkcję jednoargumentową f "przejdzie" po drzewie i zaaplikuje funkcję f do każdego węzła drzewa.

Zadanie 3

Mamy drzewo binarne takie jak w zadaniu 1 (którego węzły mają pole przechowujące wartość). Napisać funkcję której ma dwa argumenty: drzewo d i funkcję jednoargumentową f. Funkcja ta ma wyprodukować nowe drzewo, będące przekształceniem starego. Dokładniej, ma ona zamienić miejscami lewe poddrzewo z prawym, o ile wywołanie funkcji f (z argumentem będącym wartością węzła) do wartość prawdziwą. W przeciwnym razie kolejność węzłów pozostawia się bez zmian. Funkcja ma wykonać tylko jedno przejście po drzewie i nie ma zmieniać oryginalnego drzewa.

Zadanie 4

Napisać funkcję, która mając daną posortowaną tablicę liczb całkowitych zbuduje maksymalnie zrównoważone drzewo, którego kluczami są liczby z tej tablicy.

Zadanie 5

Zmodyfikować funkcję szukania elementu w drzewie uporządkowanym, tak by zwracała albo węzeł z równym kluczem (jeśli istnieje) albo, gdy klucza nie ma w drzewie to węzeł z najmniejszym kluczem większym od szukanego klucza. Jeśli szukany klucz jest większy od wszystkich kluczy w drzewie zwrócić listę pustą. Uwaga: funkcja ma wykonywać co najwyżej `O(w)' operacji gdzie `w' jest wysokością drzewa.

Zadanie 6

Napisać funkcję która "spłaszcza" wyrażenia arytmetyczne, tzn. zastępuje dwuargumentowe operatory dodawania i mnożenia wersją wieloargumentową (gdy można, tzn. jeśli argumentem sumy jest suma lub argumentem iloczynu jest iloczyn).

Zadanie 7

Zakładamy że wyrażenia logiczne są reprezentowane tak jak w zadaniu 5 z Listy 4. Napisać funkcję która mając dane wyrażenie, wartość logiczną (true lub false) i listę wartości (niektórych) zmiennych wyprodukuje nowe wyrażenie w którym ta zmienne jest zastąpione są przez podane wartości. Przy tym funkcja ta ma wykonywać "oczywiste" uproszczenia, tzn. usuwać wartość false z sumy logicznej, usuwać wartość true z iloczynu logicznego, zastępować sumę logiczną której jednym składnikiem jest true przez true, zastępować iloczyn logiczny którego czynnikiem jest false przez false. Zastanowić się jakie dodatkowe uproszczenia warto by zrobić.

Zadanie 8

Napisać funkcję "upraszczającą" wyrażenia arytmetyczne (reprezentowane przez drzewa). Funkcja ta powinna pomijać dodawanie 0 i mnożenie przez 1 oraz wykonać działania których argumentami są liczby.

Zadanie 9

Napisać funkcję która mając dane drzewo takie jak w zadaniu 1 przekształci je tak że węzły będą reprezentowane przez czteroelementowe wektory.

Zadanie 10

Zakładamy że elementy drzewa i listy mają deklaracje jak niżej:

struct drzewo {
    struct drzewo * lewe;
    struct drzewo * prawe;
    int klucz;
    int wartosc;
};
struct lista {
    struct lista * nastepny;
    int klucz;
    int wartosc;
};

Napisać funkcję która mając dane drzewo uporządkowane `d' i wartości `k1' i `k2' wyprodukuje listę tych kluczy (i odpowiadająch im wartości) które są większe lub równe `k1' i mniejsze lub równe `k2'. Innmi słowy ma to być lista kluczy (i odpowiadająch im wartości) z odcinka domkniętego od `k1' do `k2'. Uwaga: funkcja ma wykonywać co najwyżej `O(w+m)' operacji gdzie `w' jest wysokością drzewa zaś `m' jest ilością elementów wynikowej listy.