Sprawdź się

Pokaż ćwiczenia:

RL8CNGirI9nob11

Ćwiczenie 1

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

R17UWOAMMmjbV2

Ć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

Ćwiczenie 3

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

W jakiej kolejności zostaną usunięte węzły za pomocą zaprezentowanego wariantu funkcji rekurencyjnej usunDrzewo() dla opisanego poniżej drzewa binarnego. Zaznacz poprawną odpowiedź.

void usunDrzewo(Wezel* wezel) {
    if (wezel != nullptr)  {
        usunDrzewo(wezel->prawy);
        usunDrzewo(wezel->lewy);
        cout << wezel->klucz << " ";
        delete wezel;
        
    }
}

R1a2H5QXJA5oq

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

Poniżej opisano dowiązania węzłów drzewa binarnego:
Korzeń drzewa (wierzchołek sześć) posiada dwa rozgałęzienia.
Po lewej stronie łączy się z wierzchołkiem cztery.
Po prawej stronie łączy się z wierzchołkiem jedenaście.
Wierzchołek cztery posiada dwa rozgałęzienia, po lewej stronie łączy się z wierzchołkiem dwa, a po prawej stronie z wierzchołkiem pięć.
Wierzchołek jedenaście posiada dwa rozgałęzienia, po lewej stronie łączy się z wierzchołkiem osiem, a po prawej stronie z wierzchołkiem szesnaście.

RH9gEsaVziT00

Ź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:

Wezel* korzen = new Wezel(5);

korzen->lewy = new Wezel(3);
korzen->lewy->lewy = new Wezel(2);
korzen->lewy->prawy = new Wezel(4);
		
korzen->prawy = new Wezel(8);
korzen->prawy->lewy = new Wezel(7);
korzen->prawy->prawy = new Wezel(20);

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

liczba naturalna; liczba liści w drzewie binarnym

RoOPVpMxbo7Np

Przykładowe rozwiązanie zadania:

#include <iostream>

using namespace std;

class Wezel {
    public:
        int klucz;
        Wezel* lewy;
        Wezel* prawy;

        Wezel(int k) {
            klucz = k;
            lewy = nullptr;
            prawy = nullptr;
        }
};

int policzLiscie(Wezel* wezel) {
	if (wezel != nullptr) {
		if (wezel->lewy == nullptr && wezel->prawy == nullptr)
			return 1;
		else
			return policzLiscie(wezel->lewy) + policzLiscie(wezel->prawy);
	}
	else return 0;
}

void usunDrzewo(Wezel* wezel) {
	if (wezel != nullptr) {
		usunDrzewo(wezel->lewy);
		usunDrzewo(wezel->prawy);
		delete wezel;
	}
}

int main() {
	Wezel* korzen = new Wezel(5);

	korzen->lewy = new Wezel(3);
	korzen->lewy->lewy = new Wezel(2);
	korzen->lewy->prawy = new Wezel(4);
	korzen->prawy = new Wezel(8);
	korzen->prawy->lewy = new Wezel(7);
	korzen->prawy->prawy = new Wezel(20);

	cout << policzLiscie(korzen) << endl;

	usunDrzewo(korzen);
}

Ćwiczenie 5

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:

Wezel* korzen = new Wezel(5);
korzen->lewy = new Wezel(4);
korzen->prawy = new Wezel(2);

korzen->prawy->lewy = new Wezel(7);
korzen->prawy->lewy->lewy = new Wezel(5);
korzen->prawy->lewy->prawy = new Wezel(5);

korzen->lewy->prawy = new Wezel(6);
korzen->lewy->prawy->lewy = new Wezel(4);
korzen->lewy->prawy->prawy = new 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

RtKcE4iLFkTq4

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. class Wezel otwórz nawias klamrowy. Linia 6. public dwukropek. Linia 7. int klucz średnik. Linia 8. Wezel asterysk lewy średnik. Linia 9. Wezel asterysk prawy średnik. Linia 11. Wezel otwórz nawias okrągły int klucz zamknij nawias okrągły dwukropek klucz otwórz nawias okrągły klucz zamknij nawias okrągły przecinek lewy otwórz nawias okrągły nullptr zamknij nawias okrągły przecinek prawy otwórz nawias okrągły nullptr zamknij nawias okrągły otwórz nawias klamrowy zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy średnik. Linia 14. int liczSciezki otwórz nawias okrągły Wezel asterysk wezel przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. if otwórz nawias okrągły wezel wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. if otwórz nawias okrągły wezel minus zamknij nawias ostrokątny klucz zamknij nawias ostrokątny k zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. return 0 średnik. Linia 18. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 19. k znak równości k minus wezel minus zamknij nawias ostrokątny klucz średnik. Linia 20. if otwórz nawias okrągły k znak równości znak równości 0 zamknij nawias okrągły otwórz nawias klamrowy. Linia 21. return 1 średnik. Linia 22. zamknij nawias klamrowy. Linia 23. return liczSciezki otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy przecinek k zamknij nawias okrągły plus liczSciezki otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy przecinek k zamknij nawias okrągły średnik. Linia 24. zamknij nawias klamrowy. Linia 25. zamknij nawias klamrowy. Linia 26. return 0 średnik. Linia 27. zamknij nawias klamrowy. Linia 29. void usunDrzewo otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 30. if otwórz nawias okrągły wezel wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 31. usunDrzewo otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy zamknij nawias okrągły średnik. Linia 32. usunDrzewo otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 33. delete wezel średnik. Linia 34. zamknij nawias klamrowy. Linia 35. zamknij nawias klamrowy. Linia 37. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 38. Wezel asterysk korzen znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 39. korzen minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 40. korzen minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 42. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 43. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 44. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 46. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 47. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 48. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 50. cout otwórz nawias ostrokątny otwórz nawias ostrokątny liczSciezki otwórz nawias okrągły korzen przecinek 19 zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 51. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

class Wezel {
public:
    int klucz;
    Wezel* lewy;
    Wezel* prawy;

    Wezel(int klucz) : klucz(klucz), lewy(nullptr), prawy(nullptr) {}
};

int liczSciezki(Wezel* wezel, int k) {
    if (wezel != nullptr) {
        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;
}

void usunDrzewo(Wezel* wezel) {
    if (wezel != nullptr) {
        usunDrzewo(wezel->lewy);
        usunDrzewo(wezel->prawy);
        delete wezel;
    }
}

int main() {
    Wezel* korzen = new Wezel(5);
    korzen->lewy = new Wezel(4);
    korzen->prawy = new Wezel(2);

    korzen->prawy->lewy = new Wezel(7);
    korzen->prawy->lewy->lewy = new Wezel(5);
    korzen->prawy->lewy->prawy = new Wezel(5);

    korzen->lewy->prawy = new Wezel(6);
    korzen->lewy->prawy->lewy = new Wezel(4);
    korzen->lewy->prawy->prawy = new Wezel(4);

    cout << liczSciezki(korzen, 19) << endl;
}

Ćwiczenie 6

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:

Wezel* korzen = new Wezel(6);

korzen->lewy = new Wezel(4);
korzen->lewy->lewy = new Wezel(2);
korzen->lewy->lewy->lewy = new Wezel(1);
korzen->lewy->lewy->prawy = new Wezel(3);
korzen->lewy->prawy = new Wezel(5);
korzen->prawy = new Wezel(8);
korzen->prawy->lewy = new Wezel(7);
korzen->prawy->prawy = new Wezel(20);

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

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

R1ORDPtbw4OQO

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. class Wezel otwórz nawias klamrowy. Linia 6. public dwukropek. Linia 7. int klucz średnik. Linia 8. Wezel asterysk lewy średnik. Linia 9. Wezel asterysk prawy średnik. Linia 11. Wezel otwórz nawias okrągły int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. klucz znak równości k średnik. Linia 13. lewy znak równości nullptr średnik. Linia 14. prawy znak równości nullptr średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy średnik. Linia 18. int policzWezly otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. if otwórz nawias okrągły wezel wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. return 1 plus policzWezly otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy zamknij nawias okrągły plus policzWezly otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 21. zamknij nawias klamrowy. Linia 22. else return 0 średnik. Linia 23. zamknij nawias klamrowy. Linia 25. void usunDrzewo otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. if otwórz nawias okrągły wezel wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. usunDrzewo otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy zamknij nawias okrągły średnik. Linia 28. usunDrzewo otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 29. delete wezel średnik. Linia 30. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 33. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. Wezel asterysk korzen znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 36. korzen minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 37. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 38. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 39. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 40. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 41. korzen minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 42. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 43. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 20 zamknij nawias okrągły średnik. Linia 45. cout otwórz nawias ostrokątny otwórz nawias ostrokątny policzWezly otwórz nawias okrągły korzen zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 47. usunDrzewo otwórz nawias okrągły korzen zamknij nawias okrągły średnik. Linia 48. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

class Wezel {
    public:
        int klucz;
        Wezel* lewy;
        Wezel* prawy;

        Wezel(int k) {
            klucz = k;
            lewy = nullptr;
            prawy = nullptr;
        }
};

int policzWezly(Wezel* wezel) {
	if (wezel != nullptr) {
		return 1 + policzWezly(wezel->lewy) + policzWezly(wezel->prawy);
	}
	else return 0;
}

void usunDrzewo(Wezel* wezel) {
	if (wezel != nullptr) {
		usunDrzewo(wezel->lewy);
		usunDrzewo(wezel->prawy);
		delete wezel;
	}
}

int main() {
	Wezel* korzen = new Wezel(6);

	korzen->lewy = new Wezel(4);
	korzen->lewy->lewy = new Wezel(2);
	korzen->lewy->lewy->lewy = new Wezel(1);
	korzen->lewy->lewy->prawy = new Wezel(3);
	korzen->lewy->prawy = new Wezel(5);
	korzen->prawy = new Wezel(8);
	korzen->prawy->lewy = new Wezel(7);
	korzen->prawy->prawy = new Wezel(20);

	cout << policzWezly(korzen) << endl;

	usunDrzewo(korzen);
}

Ćwiczenie 7

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

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

Wezel* korzen = new Wezel(6);

korzen->lewy = new Wezel(4);
korzen->lewy->lewy = new Wezel(2);
korzen->lewy->lewy->lewy = new Wezel(1);
korzen->lewy->lewy->prawy = new Wezel(3);
korzen->lewy->prawy = new Wezel(5);
korzen->prawy = new Wezel(8);
korzen->prawy->lewy = new Wezel(7);
korzen->prawy->prawy = new Wezel(20);

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

liczba naturalna; iloczyn wszystkich kluczy drzewa

RLOY3rhF7FrFo

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. class Wezel otwórz nawias klamrowy. Linia 6. public dwukropek. Linia 7. int klucz średnik. Linia 8. Wezel asterysk lewy średnik. Linia 9. Wezel asterysk prawy średnik. Linia 11. Wezel otwórz nawias okrągły int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. klucz znak równości k średnik. Linia 13. lewy znak równości nullptr średnik. Linia 14. prawy znak równości nullptr średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy średnik. Linia 18. int iloczynKluczy otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. if otwórz nawias okrągły wezel wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. return wezel minus zamknij nawias ostrokątny klucz asterysk iloczynKluczy otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy zamknij nawias okrągły asterysk iloczynKluczy otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 21. zamknij nawias klamrowy. Linia 22. else return 1 średnik. Linia 23. zamknij nawias klamrowy. Linia 25. void usunDrzewo otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. if otwórz nawias okrągły wezel wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. usunDrzewo otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy zamknij nawias okrągły średnik. Linia 28. usunDrzewo otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 29. delete wezel średnik. Linia 30. zamknij nawias klamrowy. Linia 31. zamknij nawias klamrowy. Linia 33. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 34. Wezel asterysk korzen znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 36. korzen minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 37. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 38. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 39. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 40. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 41. korzen minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 42. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 43. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 20 zamknij nawias okrągły średnik. Linia 45. cout otwórz nawias ostrokątny otwórz nawias ostrokątny iloczynKluczy otwórz nawias okrągły korzen zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 47. usunDrzewo otwórz nawias okrągły korzen zamknij nawias okrągły średnik. Linia 48. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

class Wezel {
    public:
        int klucz;
        Wezel* lewy;
        Wezel* prawy;

        Wezel(int k) {
            klucz = k;
            lewy = nullptr;
            prawy = nullptr;
        }
};

int iloczynKluczy(Wezel* wezel) {
    if (wezel != nullptr) {
        return wezel->klucz * iloczynKluczy(wezel->lewy) * iloczynKluczy(wezel->prawy);
    }
    else return 1;
}

void usunDrzewo(Wezel* wezel) {
    if (wezel != nullptr) {
        usunDrzewo(wezel->lewy);
        usunDrzewo(wezel->prawy);
        delete wezel;
    }
}

int main() {
    Wezel* korzen = new Wezel(6);

    korzen->lewy = new Wezel(4);
    korzen->lewy->lewy = new Wezel(2);
    korzen->lewy->lewy->lewy = new Wezel(1);
    korzen->lewy->lewy->prawy = new Wezel(3);
    korzen->lewy->prawy = new Wezel(5);
    korzen->prawy = new Wezel(8);
    korzen->prawy->lewy = new Wezel(7);
    korzen->prawy->prawy = new Wezel(20);

    cout << iloczynKluczy(korzen) << endl;

    usunDrzewo(korzen);
}

Ćwiczenie 8

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:

Linia 1. Wezel asterysk korzen znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 3. korzen minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 4. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 5. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 6. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 7. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 8. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 9. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 10. korzen minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 11. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 12. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 20 zamknij nawias okrągły średnik.

Wezel* korzen = new Wezel(6);

korzen->lewy = new Wezel(4);
korzen->lewy->lewy = new Wezel(2);
korzen->lewy->lewy->lewy = new Wezel(1);
korzen->lewy->lewy->prawy = new Wezel(3);
korzen->lewy->lewy->prawy->prawy = new Wezel(3);
korzen->lewy->lewy->prawy->prawy->prawy = new Wezel(3);
korzen->lewy->prawy = new Wezel(5);
korzen->prawy = new Wezel(8);
korzen->prawy->lewy = new Wezel(7);
korzen->prawy->prawy = new Wezel(20);

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

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

RLcyezZq7vINj

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. class Wezel otwórz nawias klamrowy. Linia 6. public dwukropek. Linia 7. int klucz średnik. Linia 8. Wezel asterysk lewy średnik. Linia 9. Wezel asterysk prawy średnik. Linia 11. Wezel otwórz nawias okrągły int klucz zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. this minus zamknij nawias ostrokątny klucz znak równości klucz średnik. Linia 13. this minus zamknij nawias ostrokątny lewy znak równości nullptr średnik. Linia 14. this minus zamknij nawias ostrokątny prawy znak równości nullptr średnik. Linia 15. zamknij nawias klamrowy. Linia 16. zamknij nawias klamrowy średnik. Linia 18. int najdluzszaSciezka otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. if otwórz nawias okrągły wezel wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 20. int lewy znak równości najdluzszaSciezka otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy zamknij nawias okrągły średnik. Linia 21. int prawy znak równości najdluzszaSciezka otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 23. int maksDlugosc średnik. Linia 24. if otwórz nawias okrągły prawy zamknij nawias ostrokątny lewy zamknij nawias okrągły otwórz nawias klamrowy. Linia 25. maksDlugosc znak równości prawy średnik. Linia 26. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 27. maksDlugosc znak równości lewy średnik. Linia 28. zamknij nawias klamrowy. Linia 30. return 1 plus maksDlugosc średnik. Linia 31. zamknij nawias klamrowy. Linia 32. else return minus 1 średnik. Linia 33. zamknij nawias klamrowy. Linia 35. void usunDrzewo otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 36. if otwórz nawias okrągły wezel wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 37. usunDrzewo otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 38. usunDrzewo otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy zamknij nawias okrągły średnik. Linia 39. delete wezel średnik. Linia 40. zamknij nawias klamrowy. Linia 41. zamknij nawias klamrowy. Linia 43. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 44. Wezel asterysk korzen znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 46. korzen minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 47. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 48. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 49. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 50. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 51. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 52. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 53. korzen minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 54. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 55. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 20 zamknij nawias okrągły średnik. Linia 57. cout otwórz nawias ostrokątny otwórz nawias ostrokątny najdluzszaSciezka otwórz nawias okrągły korzen zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 59. usunDrzewo otwórz nawias okrągły korzen zamknij nawias okrągły średnik. Linia 60. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

class Wezel {
	public:
		int klucz;
		Wezel* lewy;
		Wezel* prawy;

		Wezel(int klucz) {
			this->klucz = klucz;
			this->lewy = nullptr;
			this->prawy = nullptr;
		}
};

int najdluzszaSciezka(Wezel* wezel) {
	if (wezel != nullptr) {
		int lewy = najdluzszaSciezka(wezel->lewy);
		int prawy = najdluzszaSciezka(wezel->prawy);

		int maksDlugosc;
        if (prawy > lewy) {
            maksDlugosc = prawy;
        } else {
            maksDlugosc = lewy;
        }

		return 1 + maksDlugosc;
	}
	else return -1;
}

void usunDrzewo(Wezel* wezel) {
	if (wezel != nullptr) {
		usunDrzewo(wezel->prawy);
		usunDrzewo(wezel->lewy);
		delete wezel;
	}
}

int main() {
	Wezel* korzen = new Wezel(6);

	korzen->lewy = new Wezel(4);
	korzen->lewy->lewy = new Wezel(2);
	korzen->lewy->lewy->lewy = new Wezel(1);
	korzen->lewy->lewy->prawy = new Wezel(3);
	korzen->lewy->lewy->prawy->prawy = new Wezel(3);
	korzen->lewy->lewy->prawy->prawy->prawy = new Wezel(3);
	korzen->lewy->prawy = new Wezel(5);
	korzen->prawy = new Wezel(8);
	korzen->prawy->lewy = new Wezel(7);
	korzen->prawy->prawy = new Wezel(20);

	cout << najdluzszaSciezka(korzen) << endl;

	usunDrzewo(korzen);
}

Ć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:

Linia 1. Wezel asterysk korzen znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 3. korzen minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 4. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 5. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 6. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 7. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 8. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 9. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 11. korzen minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 12. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 10 zamknij nawias okrągły średnik. Linia 13. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 9 zamknij nawias okrągły średnik.

Wezel* korzen = new Wezel(7);

korzen->lewy = new Wezel(5);
korzen->lewy->lewy = new Wezel(2);
korzen->lewy->prawy = new Wezel(6);
korzen->lewy->lewy->lewy = new Wezel(1);
korzen->lewy->lewy->lewy->lewy = new Wezel(1);
korzen->lewy->lewy->lewy->lewy->lewy = new Wezel(1);
korzen->lewy->lewy->prawy = new Wezel(4);

korzen->prawy = new Wezel(8);
korzen->prawy->prawy = new Wezel(10);
korzen->prawy->prawy->lewy = new Wezel(9);

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

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

R1U5kLO1TQ8dX

Przykładowe rozwiązanie zadania:

Linia 1. kratka include otwórz nawias ostrokątny iostream zamknij nawias ostrokątny. Linia 3. using namespace std średnik. Linia 5. class Wezel otwórz nawias klamrowy. Linia 6. public dwukropek. Linia 7. int klucz średnik. Linia 8. Wezel asterysk lewy średnik. Linia 9. Wezel asterysk prawy średnik. Linia 11. Wezel otwórz nawias okrągły int klucz zamknij nawias okrągły dwukropek klucz otwórz nawias okrągły klucz zamknij nawias okrągły przecinek lewy otwórz nawias okrągły nullptr zamknij nawias okrągły przecinek prawy otwórz nawias okrągły nullptr zamknij nawias okrągły otwórz nawias klamrowy zamknij nawias klamrowy. Linia 12. zamknij nawias klamrowy średnik. Linia 14. int policzOjcowZJednymSynem otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. if otwórz nawias okrągły wezel wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 16. if otwórz nawias okrągły otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy znak równości znak równości nullptr ampersant ampersant wezel minus zamknij nawias ostrokątny prawy wykrzyknik znak równości nullptr zamknij nawias okrągły kreska pionowa kreska pionowa otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy znak równości znak równości nullptr ampersant ampersant wezel minus zamknij nawias ostrokątny lewy wykrzyknik znak równości nullptr zamknij nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. return 1 plus policzOjcowZJednymSynem otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy zamknij nawias okrągły plus policzOjcowZJednymSynem otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 18. zamknij nawias klamrowy. Linia 19. return policzOjcowZJednymSynem otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy zamknij nawias okrągły plus policzOjcowZJednymSynem otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 20. zamknij nawias klamrowy. Linia 21. return 0 średnik. Linia 22. zamknij nawias klamrowy. Linia 24. void usunDrzewo otwórz nawias okrągły Wezel asterysk wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 25. if otwórz nawias okrągły wezel wykrzyknik znak równości nullptr zamknij nawias okrągły otwórz nawias klamrowy. Linia 26. usunDrzewo otwórz nawias okrągły wezel minus zamknij nawias ostrokątny lewy zamknij nawias okrągły średnik. Linia 27. usunDrzewo otwórz nawias okrągły wezel minus zamknij nawias ostrokątny prawy zamknij nawias okrągły średnik. Linia 28. delete wezel średnik. Linia 29. zamknij nawias klamrowy. Linia 30. zamknij nawias klamrowy. Linia 32. int main otwórz nawias okrągły zamknij nawias okrągły otwórz nawias klamrowy. Linia 33. Wezel asterysk korzen znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 35. korzen minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 36. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 37. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 38. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 39. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 40. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 41. korzen minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny lewy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 43. korzen minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 44. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy znak równości new Wezel otwórz nawias okrągły 10 zamknij nawias okrągły średnik. Linia 45. korzen minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny prawy minus zamknij nawias ostrokątny lewy znak równości new Wezel otwórz nawias okrągły 9 zamknij nawias okrągły średnik. Linia 47. cout otwórz nawias ostrokątny otwórz nawias ostrokątny policzOjcowZJednymSynem otwórz nawias okrągły korzen zamknij nawias okrągły otwórz nawias ostrokątny otwórz nawias ostrokątny endl średnik. Linia 49. usunDrzewo otwórz nawias okrągły korzen zamknij nawias okrągły średnik. Linia 51. return 0 średnik. Linia 52. zamknij nawias klamrowy.

#include <iostream>

using namespace std;

class Wezel {
public:
    int klucz;
    Wezel* lewy;
    Wezel* prawy;

    Wezel(int klucz) : klucz(klucz), lewy(nullptr), prawy(nullptr) {}
};

int policzOjcowZJednymSynem(Wezel* wezel) {
    if (wezel != nullptr) {
        if ((wezel->lewy == nullptr && wezel->prawy != nullptr) || (wezel->prawy == nullptr && wezel->lewy != nullptr)) {
            return 1 + policzOjcowZJednymSynem(wezel->lewy) + policzOjcowZJednymSynem(wezel->prawy);
        }
        return policzOjcowZJednymSynem(wezel->lewy) + policzOjcowZJednymSynem(wezel->prawy);
    }
    return 0;
}

void usunDrzewo(Wezel* wezel) {
    if (wezel != nullptr) {
        usunDrzewo(wezel->lewy);
        usunDrzewo(wezel->prawy);
        delete wezel;
    }
}

int main() {
    Wezel* korzen = new Wezel(7);

    korzen->lewy = new Wezel(5);
    korzen->lewy->lewy = new Wezel(2);
    korzen->lewy->prawy = new Wezel(6);
    korzen->lewy->lewy->lewy = new Wezel(1);
    korzen->lewy->lewy->lewy->lewy = new Wezel(1);
    korzen->lewy->lewy->lewy->lewy->lewy = new Wezel(1);
    korzen->lewy->lewy->prawy = new Wezel(4);

    korzen->prawy = new Wezel(8);
    korzen->prawy->prawy = new Wezel(10);
    korzen->prawy->prawy->lewy = new Wezel(9);

    cout << policzOjcowZJednymSynem(korzen) << endl;

    usunDrzewo(korzen);

    return 0;
}

Prezentacja multimedialna

Dla nauczyciela