Sprawdź się

Pokaż ćwiczenia:

Ćwiczenie 1

RL8CNGirI9nob11

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

R3dGdvQMXxjUf1

Dla przedstawionego opisu drzewa binarnego zdefiniowano referencję do korzenia korzen. Wskaż właściwy ciąg odwołań do synów. Ciąg ten ma kierować do węzła o kluczu 19.
Wierzchołek. 12. Odnoga w lewo. 8. Odnoga w lewo od 8. 5. Odnoga w prawo od 8. 9. Odnoga w lewo od 5. 1. Odnoga w prawo od 5. 7. Odnoga w prawo od 9. 11. Odnoga w prawo od wierzchołka 12. 20. Odnloga w lewo od 20. 13. Odnloga w prawo od 20. 22. Odnoga w prawo od 13. 19. Odnoga w lewo od 22. 21. Odnoga w prawo od 22. 24.

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

R14CKlmOP4FP92

Ćwiczenie 2

Wywołano funkcję inorderWalk() przekazując przez argument wskaźnik root do korzenia pewnego drzewa binarnego. Uporządkuj klucze w kolejniości według, której zostały wypisane w konsoli przez funkcję inorderWalk(). Elementy do uszeregowania: 1. root->right->key, 2. root->left->right->key, 3. root->left->left->key, 4. root->left->right->right->right->key, 5. root->left->right->right->key, 6. root->right->left->key, 7. root->left->key, 8. root->key

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ćwiczenie 3

Oznacz na rysunku, w jakiej kolejności zostaną usunięte węzły za pomocą zaprezentowanego wariantu funkcji rekurencyjnej usunDrzewo().

def usunDrzewo(wezel):
    if wezel is not None:
        usunDrzewo(wezel.prawy)
        usunDrzewo(wezel.lewy)
        print(wezel.klucz, end=" ")

R1a2H5QXJA5oq2

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

R1GqAGH8JlpQe

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Ćwiczenie 4

Zapisz program, który dla danego drzewa binarnego obliczy, ile znajduje się w nim liści.

Działanie programu przetestuj dla następującego drzewa:

korzen = Wezel(5)
korzen.lewy = Wezel(3)
korzen.lewy.lewy = Wezel(2)
korzen.lewy.prawy = Wezel(4)
korzen.prawy = Wezel(8)
korzen.prawy.lewy = Wezel(7)
korzen.prawy.prawy = Wezel(20)

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

liczba naturalna; liczba liści w drzewie binarnym

R1NK0uJ5BsTDj

Przykładowe rozwiązanie zadania:

class Wezel:
    def __init__(self, klucz):
        self.klucz = klucz
        self.lewy = None
        self.prawy = None

def policzLiscie(wezel):
    if wezel is not None:
        if wezel.lewy is None and wezel.prawy is None:
            return 1
        else:
            return policzLiscie(wezel.lewy) + policzLiscie(wezel.prawy)
    else:
        return 0

korzen = Wezel(5)
korzen.lewy = Wezel(3)
korzen.lewy.lewy = Wezel(2)
korzen.lewy.prawy = Wezel(4)
korzen.prawy = Wezel(8)
korzen.prawy.lewy = Wezel(7)
korzen.prawy.prawy = Wezel(20)

print(policzLiscie(korzen))

Ćwiczenie 5

Zapisz program, który dla danego drzewa binarnego obliczy, ile znajduje się w nim węzłów.

Działanie programu przetestuj dla następującego drzewa:

korzen = Wezel(6)
korzen.lewy = Wezel(4)
korzen.lewy.lewy = Wezel(2)
korzen.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.prawy = Wezel(3)
korzen.lewy.prawy = Wezel(5)
korzen.prawy = Wezel(8)
korzen.prawy.lewy = Wezel(7)
korzen.prawy.prawy = Wezel(20)

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

liczba naturalna; liczba węzłów w drzewie binarnym

Rpkwh2HGb1FGo

Przykładowe rozwiązanie zadania:

class Wezel:
    def __init__(self, klucz):
        self.klucz = klucz
        self.lewy = None
        self.prawy = None

def policzWezly(wezel):
    if wezel is not None:
        return 1 + policzWezly(wezel.lewy) + policzWezly(wezel.prawy)
    else:
        return 0

korzen = Wezel(6)
korzen.lewy = Wezel(4)
korzen.lewy.lewy = Wezel(2)
korzen.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.prawy = Wezel(3)
korzen.lewy.prawy = Wezel(5)
korzen.prawy = Wezel(8)
korzen.prawy.lewy = Wezel(7)
korzen.prawy.prawy = Wezel(20)

print(policzWezly(korzen))

Ćwiczenie 6

Zapisz program, który dla danego drzewa binarnego obliczy i wypisze iloczyn wszystkich jego kluczy.

Działanie programu przetestuj dla następującego drzewa:

korzen = Wezel(6)
korzen.lewy = Wezel(4)
korzen.lewy.lewy = Wezel(2)
korzen.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.prawy = Wezel(3)
korzen.lewy.prawy = Wezel(5)
korzen.prawy = Wezel(8)
korzen.prawy.lewy = Wezel(7)
korzen.prawy.prawy = Wezel(20)

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

liczba naturalna; iloczyn wszystkich kluczy drzewa

R1Pabq6875rhg

Przykładowe rozwiązanie zadania:

class Wezel:
    def __init__(self, klucz):
        self.klucz = klucz
        self.lewy = None
        self.prawy = None

def iloczynKluczy(wezel):
    if wezel is not None:
        return wezel.klucz * iloczynKluczy(wezel.lewy) * iloczynKluczy(wezel.prawy)
    else:
        return 1

korzen = Wezel(6)
korzen.lewy = Wezel(4)
korzen.lewy.lewy = Wezel(2)
korzen.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.prawy = Wezel(3)
korzen.lewy.prawy = Wezel(5)
korzen.prawy = Wezel(8)
korzen.prawy.lewy = Wezel(7)
korzen.prawy.prawy = Wezel(20)

print(iloczynKluczy(korzen))

Ćwiczenie 7

Zapisz program, który dla danego drzewa binarnego wypisze długość najdłuższej ścieżki, która zaczynałaby się w korzeniu drzewa. Przez każdy węzeł można przejść tylko raz, a długość każdej krawędzi wynosi 1.

Działanie programu przetestuj dla następującego drzewa:

korzen = Wezel(6)
korzen.lewy = Wezel(4)
korzen.lewy.lewy = Wezel(2)
korzen.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.prawy = Wezel(3)
korzen.lewy.lewy.prawy.prawy = Wezel(3)
korzen.lewy.lewy.prawy.prawy.prawy = Wezel(3)
korzen.lewy.prawy = Wezel(5)
korzen.prawy = Wezel(8)
korzen.prawy.lewy = Wezel(7)
korzen.prawy.prawy = Wezel(20)

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

liczba naturalna; długość najdłuższej ścieżki zaczynającej się w korzeniu drzewa binarnego

RDYh7kLMnAaPV

Przykładowe rozwiązanie zadania:

Linia 1. class Wezel dwukropek. Linia 2. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self przecinek klucz zamknij nawias okrągły dwukropek. Linia 3. self kropka klucz znak równości klucz. Linia 4. self kropka lewy znak równości None. Linia 5. self kropka prawy znak równości None. Linia 7. def najdluzszaSciezka otwórz nawias okrągły wezel zamknij nawias okrągły dwukropek. Linia 8. if wezel is not None dwukropek. Linia 9. lewy znak równości najdluzszaSciezka otwórz nawias okrągły wezel kropka lewy zamknij nawias okrągły. Linia 10. prawy znak równości najdluzszaSciezka otwórz nawias okrągły wezel kropka prawy zamknij nawias okrągły. Linia 11. return 1 plus max otwórz nawias okrągły lewy przecinek prawy zamknij nawias okrągły. Linia 12. else dwukropek. Linia 13. return minus 1. Linia 15. korzen znak równości Wezel otwórz nawias okrągły 6 zamknij nawias okrągły. Linia 16. korzen kropka lewy znak równości Wezel otwórz nawias okrągły 4 zamknij nawias okrągły. Linia 17. korzen kropka lewy kropka lewy znak równości Wezel otwórz nawias okrągły 2 zamknij nawias okrągły. Linia 18. korzen kropka lewy kropka lewy kropka lewy znak równości Wezel otwórz nawias okrągły 1 zamknij nawias okrągły. Linia 19. korzen kropka lewy kropka lewy kropka prawy znak równości Wezel otwórz nawias okrągły 3 zamknij nawias okrągły. Linia 20. korzen kropka lewy kropka lewy kropka prawy kropka prawy znak równości Wezel otwórz nawias okrągły 3 zamknij nawias okrągły. Linia 21. korzen kropka lewy kropka lewy kropka prawy kropka prawy kropka prawy znak równości Wezel otwórz nawias okrągły 3 zamknij nawias okrągły. Linia 22. korzen kropka lewy kropka prawy znak równości Wezel otwórz nawias okrągły 5 zamknij nawias okrągły. Linia 23. korzen kropka prawy znak równości Wezel otwórz nawias okrągły 8 zamknij nawias okrągły. Linia 24. korzen kropka prawy kropka lewy znak równości Wezel otwórz nawias okrągły 7 zamknij nawias okrągły. Linia 25. korzen kropka prawy kropka prawy znak równości Wezel otwórz nawias okrągły 20 zamknij nawias okrągły. Linia 27. print otwórz nawias okrągły najdluzszaSciezka otwórz nawias okrągły korzen zamknij nawias okrągły zamknij nawias okrągły.

class Wezel:
    def __init__(self, klucz):
        self.klucz = klucz
        self.lewy = None
        self.prawy = None

def najdluzszaSciezka(wezel):
    if wezel is not None:
        lewy = najdluzszaSciezka(wezel.lewy)
        prawy = najdluzszaSciezka(wezel.prawy)
        return 1 + max(lewy, prawy)
    else:
        return -1

korzen = Wezel(6)
korzen.lewy = Wezel(4)
korzen.lewy.lewy = Wezel(2)
korzen.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.prawy = Wezel(3)
korzen.lewy.lewy.prawy.prawy = Wezel(3)
korzen.lewy.lewy.prawy.prawy.prawy = Wezel(3)
korzen.lewy.prawy = Wezel(5)
korzen.prawy = Wezel(8)
korzen.prawy.lewy = Wezel(7)
korzen.prawy.prawy = Wezel(20)

print(najdluzszaSciezka(korzen))

Ćwiczenie 8

Napisz program, który dla danego drzewa binarnego obliczy i wypisze liczbę wszystkich ścieżek z korzenia drzewa do węzłów potomnych tak, aby suma kluczy węzłów była równa liczbie naturalnej k.

Działanie programu przetestuj dla k = 19 oraz następującego drzewa:

korzen = Wezel(5)
korzen.lewy = Wezel(4)
korzen.prawy = Wezel(2)

korzen.prawy.lewy = Wezel(7)
korzen.prawy.lewy.lewy = Wezel(5)
korzen.prawy.lewy.prawy = Wezel(5)

korzen.lewy.prawy = Wezel(6)
korzen.lewy.prawy.lewy = Wezel(4)
korzen.lewy.prawy.prawy = Wezel(4)

Specyfikacja problemu:

Dane:

drzewo binarne
k – liczba naturalna; suma wartości węzłów

Wynik:

liczbaSciezek – liczba naturalna; liczba ścieżek, którymi można osiągnąć sumę wartości węzłów k

RQ3JvdMhtBH7m

Przykładowe rozwiązanie zadania:

Linia 1. class Wezel dwukropek. Linia 2. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self przecinek klucz zamknij nawias okrągły dwukropek. Linia 3. self kropka klucz znak równości klucz. Linia 4. self kropka lewy znak równości None. Linia 5. self kropka prawy znak równości None. Linia 7. def liczSciezki otwórz nawias okrągły wezel przecinek k zamknij nawias okrągły dwukropek. Linia 8. if wezel is not None dwukropek. Linia 9. if wezel kropka klucz zamknij nawias ostrokątny k dwukropek. Linia 10. return 0. Linia 11. else dwukropek. Linia 12. k znak równości k minus wezel kropka klucz. Linia 13. if k znak równości znak równości 0 dwukropek. Linia 14. return 1. Linia 15. return liczSciezki otwórz nawias okrągły wezel kropka lewy przecinek k zamknij nawias okrągły plus liczSciezki otwórz nawias okrągły wezel kropka prawy przecinek k zamknij nawias okrągły. Linia 16. return 0. Linia 18. korzen znak równości Wezel otwórz nawias okrągły 5 zamknij nawias okrągły. Linia 19. korzen kropka lewy znak równości Wezel otwórz nawias okrągły 4 zamknij nawias okrągły. Linia 20. korzen kropka prawy znak równości Wezel otwórz nawias okrągły 2 zamknij nawias okrągły. Linia 22. korzen kropka prawy kropka lewy znak równości Wezel otwórz nawias okrągły 7 zamknij nawias okrągły. Linia 23. korzen kropka prawy kropka lewy kropka lewy znak równości Wezel otwórz nawias okrągły 5 zamknij nawias okrągły. Linia 24. korzen kropka prawy kropka lewy kropka prawy znak równości Wezel otwórz nawias okrągły 5 zamknij nawias okrągły. Linia 26. korzen kropka lewy kropka prawy znak równości Wezel otwórz nawias okrągły 6 zamknij nawias okrągły. Linia 27. korzen kropka lewy kropka prawy kropka lewy znak równości Wezel otwórz nawias okrągły 4 zamknij nawias okrągły. Linia 28. korzen kropka lewy kropka prawy kropka prawy znak równości Wezel otwórz nawias okrągły 4 zamknij nawias okrągły. Linia 30. print otwórz nawias okrągły liczSciezki otwórz nawias okrągły korzen przecinek 19 zamknij nawias okrągły zamknij nawias okrągły.

class Wezel:
    def __init__(self, klucz):
        self.klucz = klucz
        self.lewy = None
        self.prawy = None

def liczSciezki(wezel, k):
    if wezel is not None:
        if wezel.klucz > k:
            return 0
        else:
            k = k - wezel.klucz
            if k == 0:
                return 1
            return liczSciezki(wezel.lewy, k) + liczSciezki(wezel.prawy, k)
    return 0

korzen = Wezel(5)
korzen.lewy = Wezel(4)
korzen.prawy = Wezel(2)

korzen.prawy.lewy = Wezel(7)
korzen.prawy.lewy.lewy = Wezel(5)
korzen.prawy.lewy.prawy = Wezel(5)

korzen.lewy.prawy = Wezel(6)
korzen.lewy.prawy.lewy = Wezel(4)
korzen.lewy.prawy.prawy = Wezel(4)

print(liczSciezki(korzen, 19))

Ćwiczenie 9

Napisz program, który dla danego drzewa binarnego obliczy, ile węzłów ma tylko jednego syna, oraz zwróci ich liczbę.

Działanie programu przetestuj dla następującego drzewa:

korzen = Wezel(7)
korzen.lewy = Wezel(5)
korzen.lewy.lewy = Wezel(2)
korzen.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.prawy = Wezel(4)
korzen.lewy.prawy = Wezel(6)
korzen.prawy = Wezel(8)
korzen.prawy.prawy = Wezel(10)
korzen.prawy.prawy.lewy = Wezel(9)

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

liczbaOjcow – liczba naturalna; liczba ojców w drzewie binarnym, którzy mają dokładnie jednego syna

R3XloYfk8zqOg

Przykładowe rozwiązanie zadania:

Linia 1. class Wezel dwukropek. Linia 2. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self przecinek klucz zamknij nawias okrągły dwukropek. Linia 3. self kropka klucz znak równości klucz. Linia 4. self kropka lewy znak równości None. Linia 5. self kropka prawy znak równości None. Linia 7. def policzOjcowZJednymSynem otwórz nawias okrągły wezel zamknij nawias okrągły dwukropek. Linia 8. if wezel is not None dwukropek. Linia 9. if otwórz nawias okrągły wezel kropka lewy is None and wezel kropka prawy is not None zamknij nawias okrągły or otwórz nawias okrągły wezel kropka prawy is None and wezel kropka lewy is not None zamknij nawias okrągły dwukropek. Linia 10. return 1 plus policzOjcowZJednymSynem otwórz nawias okrągły wezel kropka lewy zamknij nawias okrągły plus policzOjcowZJednymSynem otwórz nawias okrągły wezel kropka prawy zamknij nawias okrągły. Linia 11. return policzOjcowZJednymSynem otwórz nawias okrągły wezel kropka lewy zamknij nawias okrągły plus policzOjcowZJednymSynem otwórz nawias okrągły wezel kropka prawy zamknij nawias okrągły. Linia 12. return 0. Linia 14. korzen znak równości Wezel otwórz nawias okrągły 7 zamknij nawias okrągły. Linia 15. korzen kropka lewy znak równości Wezel otwórz nawias okrągły 5 zamknij nawias okrągły. Linia 16. korzen kropka lewy kropka lewy znak równości Wezel otwórz nawias okrągły 2 zamknij nawias okrągły. Linia 17. korzen kropka lewy kropka lewy kropka lewy znak równości Wezel otwórz nawias okrągły 1 zamknij nawias okrągły. Linia 18. korzen kropka lewy kropka lewy kropka lewy kropka lewy znak równości Wezel otwórz nawias okrągły 1 zamknij nawias okrągły. Linia 19. korzen kropka lewy kropka lewy kropka lewy kropka lewy kropka lewy znak równości Wezel otwórz nawias okrągły 1 zamknij nawias okrągły. Linia 20. korzen kropka lewy kropka lewy kropka prawy znak równości Wezel otwórz nawias okrągły 4 zamknij nawias okrągły. Linia 21. korzen kropka lewy kropka prawy znak równości Wezel otwórz nawias okrągły 6 zamknij nawias okrągły. Linia 22. korzen kropka prawy znak równości Wezel otwórz nawias okrągły 8 zamknij nawias okrągły. Linia 23. korzen kropka prawy kropka prawy znak równości Wezel otwórz nawias okrągły 10 zamknij nawias okrągły. Linia 24. korzen kropka prawy kropka prawy kropka lewy znak równości Wezel otwórz nawias okrągły 9 zamknij nawias okrągły. Linia 26. print otwórz nawias okrągły policzOjcowZJednymSynem otwórz nawias okrągły korzen zamknij nawias okrągły zamknij nawias okrągły.

class Wezel:
    def __init__(self, klucz):
        self.klucz = klucz
        self.lewy = None
        self.prawy = None

def policzOjcowZJednymSynem(wezel):
    if wezel is not None:
        if (wezel.lewy is None and wezel.prawy is not None) or (wezel.prawy is None and wezel.lewy is not None):
            return 1 + policzOjcowZJednymSynem(wezel.lewy) + policzOjcowZJednymSynem(wezel.prawy)
        return policzOjcowZJednymSynem(wezel.lewy) + policzOjcowZJednymSynem(wezel.prawy)
    return 0

korzen = Wezel(7)
korzen.lewy = Wezel(5)
korzen.lewy.lewy = Wezel(2)
korzen.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.lewy.lewy.lewy = Wezel(1)
korzen.lewy.lewy.prawy = Wezel(4)
korzen.lewy.prawy = Wezel(6)
korzen.prawy = Wezel(8)
korzen.prawy.prawy = Wezel(10)
korzen.prawy.prawy.lewy = Wezel(9)

print(policzOjcowZJednymSynem(korzen))

Prezentacja multimedialna

Dla nauczyciela