Sprawdź się

Pokaż ćwiczenia:

RL8CNGirI9nob11

Ćwiczenie 1

Ź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().

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ź.

public static void usunDrzewo(Wezel wezel) {
	if (wezel != null) {
		usunDrzewo(wezel.lewy);
		usunDrzewo(wezel.prawy);
		wezel.lewy = null;
        wezel.prawy = null;
	}
}

R1a2H5QXJA5oq

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

Ćwiczenie alternatywne wyświetla się w trybie dostępności.

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.

R1XFcg6SiwOZA

Ź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

Rggr1TQdc7B7E

Przykładowe rozwiązanie zadania:

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int klucz średnik. Linia 3. Wezel lewy przecinek prawy średnik. Linia 5. Wezel otwórz nawias okrągły int klucz zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. this kropka klucz znak równości klucz średnik. Linia 7. lewy znak równości prawy znak równości null średnik. Linia 8. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. public class DrzewoBinarne otwórz nawias klamrowy. Linia 12. static int policzLiscie otwórz nawias okrągły Wezel wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły wezel wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. if otwórz nawias okrągły wezel kropka lewy znak równości znak równości wezel kropka prawy zamknij nawias okrągły. Linia 15. return 1 średnik. Linia 16. else. Linia 17. return policzLiscie otwórz nawias okrągły wezel kropka lewy zamknij nawias okrągły plus policzLiscie otwórz nawias okrągły wezel kropka prawy zamknij nawias okrągły średnik. Linia 18. zamknij nawias klamrowy. Linia 19. else return 0 średnik. Linia 20. zamknij nawias klamrowy. Linia 22. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. Wezel korzen znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 25. korzen kropka lewy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 26. korzen kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 27. korzen kropka lewy kropka prawy znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 28. korzen kropka lewy kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 29. korzen kropka lewy kropka lewy kropka prawy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 31. korzen kropka prawy znak równości new Wezel otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 32. korzen kropka prawy kropka prawy znak równości new Wezel otwórz nawias okrągły 9 zamknij nawias okrągły średnik. Linia 33. korzen kropka prawy kropka prawy kropka lewy znak równości new Wezel otwórz nawias okrągły 9 zamknij nawias okrągły średnik. Linia 34. korzen kropka prawy kropka prawy kropka prawy znak równości new Wezel otwórz nawias okrągły 9 zamknij nawias okrągły średnik. Linia 36. System kropka out kropka println otwórz nawias okrągły policzLiscie otwórz nawias okrągły korzen zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 37. zamknij nawias klamrowy. Linia 38. zamknij nawias klamrowy.

class Wezel {
	int klucz;
	Wezel lewy, prawy;

	Wezel(int klucz) {
		this.klucz = klucz;
		lewy = prawy = null;
	}
}

public class DrzewoBinarne {
    static int policzLiscie(Wezel wezel) {
        if (wezel != null) {
            if (wezel.lewy == wezel.prawy)
                return 1;
            else
                return policzLiscie(wezel.lewy) + policzLiscie(wezel.prawy);
        }
        else return 0;
    }

	public static void main(String[] args) {
		Wezel korzen = new Wezel(7);

		korzen.lewy = new Wezel(5);
		korzen.lewy.lewy = new Wezel(3);
		korzen.lewy.prawy = new Wezel(6);
		korzen.lewy.lewy.lewy = new Wezel(2);
		korzen.lewy.lewy.prawy = new Wezel(4);

		korzen.prawy = new Wezel(8);
		korzen.prawy.prawy = new Wezel(9);
		korzen.prawy.prawy.lewy = new Wezel(9);
		korzen.prawy.prawy.prawy = new Wezel(9);

		System.out.println(policzLiscie(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.lewy.prawy = new Wezel(6);
korzen.lewy.prawy.lewy = new Wezel(4);
korzen.lewy.prawy.prawy = 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);

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

R1ZDB7Fn13TES

Przykładowe rozwiązanie zadania:

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int klucz średnik. Linia 3. Wezel lewy przecinek prawy średnik. Linia 5. Wezel otwórz nawias okrągły int klucz zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. this kropka klucz znak równości klucz średnik. Linia 7. lewy znak równości prawy znak równości null średnik. Linia 8. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. public class DrzewoBinarne otwórz nawias klamrowy. Linia 12. static int liczSciezki otwórz nawias okrągły Wezel wezel przecinek int k zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły wezel wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. if otwórz nawias okrągły wezel kropka klucz zamknij nawias ostrokątny k zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. return 0 średnik. Linia 16. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 17. k znak równości k minus wezel kropka klucz średnik. Linia 18. 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 19. return 1 średnik. Linia 20. zamknij nawias klamrowy. Linia 21. 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 średnik. Linia 22. zamknij nawias klamrowy. Linia 23. zamknij nawias klamrowy. Linia 24. return 0 średnik. Linia 25. zamknij nawias klamrowy. Linia 27. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 28. Wezel korzen znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 29. korzen kropka lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 30. korzen kropka prawy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 32. korzen kropka prawy kropka lewy znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 33. korzen kropka prawy kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 34. korzen kropka prawy kropka lewy kropka prawy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 36. korzen kropka lewy kropka prawy znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 37. korzen kropka lewy kropka prawy kropka lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 38. korzen kropka lewy kropka prawy kropka prawy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 40. System kropka out kropka println 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 średnik. Linia 41. zamknij nawias klamrowy. Linia 42. zamknij nawias klamrowy.

class Wezel {
	int klucz;
	Wezel lewy, prawy;

	Wezel(int klucz) {
		this.klucz = klucz;
		lewy = prawy = null;
	}
}

public class DrzewoBinarne {
    static int liczSciezki(Wezel wezel, int k){
        if (wezel != null) {
            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;
    }
    
	public static void main(String[] args) {
		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);

		System.out.println(liczSciezki(korzen, 19));
	}
}

Ć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);

Specyfikacja problemu:

Dane:

drzewo binarne

Wynik:

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

R1URES1y04r7V

Przykładowe rozwiązanie zadania:

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int klucz średnik. Linia 3. Wezel lewy przecinek prawy średnik. Linia 5. public Wezel otwórz nawias okrągły int klucz zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. this kropka klucz znak równości klucz średnik. Linia 7. this kropka lewy znak równości null średnik. Linia 8. this kropka prawy znak równości null średnik. Linia 9. zamknij nawias klamrowy. Linia 10. zamknij nawias klamrowy. Linia 12. public class Main otwórz nawias klamrowy. Linia 13. public static int policzWezly otwórz nawias okrągły Wezel wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. if otwórz nawias okrągły wezel wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. return 1 plus policzWezly otwórz nawias okrągły wezel kropka lewy zamknij nawias okrągły plus policzWezly otwórz nawias okrągły wezel kropka prawy zamknij nawias okrągły średnik. Linia 16. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 17. return 0 średnik. Linia 18. zamknij nawias klamrowy. Linia 19. zamknij nawias klamrowy. Linia 21. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 22. Wezel korzen znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 23. korzen kropka lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 24. korzen kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 25. korzen kropka lewy kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 26. korzen kropka lewy kropka lewy kropka prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 27. korzen kropka lewy kropka prawy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 28. korzen kropka prawy znak równości new Wezel otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 29. korzen kropka prawy kropka lewy znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 30. korzen kropka prawy kropka prawy znak równości new Wezel otwórz nawias okrągły 20 zamknij nawias okrągły średnik. Linia 32. System kropka out kropka println otwórz nawias okrągły policzWezly otwórz nawias okrągły korzen zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 33. zamknij nawias klamrowy. Linia 34. zamknij nawias klamrowy.

class Wezel {
    int klucz;
    Wezel lewy, prawy;

    public Wezel(int klucz) {
        this.klucz = klucz;
        this.lewy = null;
        this.prawy = null;
    }
}

public class Main {
    public static int policzWezly(Wezel wezel) {
        if (wezel != null) {
            return 1 + policzWezly(wezel.lewy) + policzWezly(wezel.prawy);
        } else {
            return 0;
        }
    }

    public static void main(String[] args) {
        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);

        System.out.println(policzWezly(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

RJR9BLVinyEU1

Przykładowe rozwiązanie zadania:

class Wezel {
    int klucz;
    Wezel lewy, prawy;

    Wezel(int klucz) {
        this.klucz = klucz;
        lewy = prawy = null;
    }
}

public class Main {
    static int iloczynKluczy(Wezel wezel) {
        if (wezel != null) {
            return wezel.klucz * iloczynKluczy(wezel.lewy) * iloczynKluczy(wezel.prawy);
        }
        else return 1;
    }

    public static void main(String[] args) {
        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);

        System.out.println(iloczynKluczy(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:

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

RBJcu2CcPalzI

Przykładowe rozwiązanie zadania:

Linia 1. public class Wezel otwórz nawias klamrowy. Linia 2. int klucz średnik. Linia 3. Wezel lewy przecinek prawy średnik. Linia 5. public Wezel otwórz nawias okrągły int klucz zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. this kropka klucz znak równości klucz średnik. Linia 7. this kropka lewy znak równości null średnik. Linia 8. this kropka prawy znak równości null średnik. Linia 9. zamknij nawias klamrowy. Linia 11. public static int najdluzszaSciezka otwórz nawias okrągły Wezel wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 12. if otwórz nawias okrągły wezel wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. int lewy znak równości najdluzszaSciezka otwórz nawias okrągły wezel kropka lewy zamknij nawias okrągły średnik. Linia 14. int prawy znak równości najdluzszaSciezka otwórz nawias okrągły wezel kropka prawy zamknij nawias okrągły średnik. Linia 16. return 1 plus Math kropka max otwórz nawias okrągły lewy przecinek prawy zamknij nawias okrągły średnik. Linia 17. zamknij nawias klamrowy else otwórz nawias klamrowy. Linia 18. return minus 1 średnik. Linia 19. zamknij nawias klamrowy. Linia 20. zamknij nawias klamrowy. Linia 22. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 23. Wezel korzen znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 24. korzen kropka lewy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 25. korzen kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 26. korzen kropka lewy kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 27. korzen kropka lewy kropka lewy kropka prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 28. korzen kropka lewy kropka lewy kropka prawy kropka prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 29. korzen kropka lewy kropka lewy kropka prawy kropka prawy kropka prawy znak równości new Wezel otwórz nawias okrągły 3 zamknij nawias okrągły średnik. Linia 30. korzen kropka lewy kropka prawy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 31. korzen kropka prawy znak równości new Wezel otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 32. korzen kropka prawy kropka lewy znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 33. korzen kropka prawy kropka prawy znak równości new Wezel otwórz nawias okrągły 20 zamknij nawias okrągły średnik. Linia 35. System kropka out kropka println otwórz nawias okrągły najdluzszaSciezka otwórz nawias okrągły korzen zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 36. zamknij nawias klamrowy. Linia 37. zamknij nawias klamrowy.

public class Wezel {
    int klucz;
    Wezel lewy, prawy;

    public Wezel(int klucz) {
        this.klucz = klucz;
        this.lewy = null;
        this.prawy = null;
    }

    public static int najdluzszaSciezka(Wezel wezel) {
        if (wezel != null) {
            int lewy = najdluzszaSciezka(wezel.lewy);
            int prawy = najdluzszaSciezka(wezel.prawy);

            return 1 + Math.max(lewy, prawy);
        } else {
            return -1;
        }
    }

    public static void main(String[] args) {
        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);

        System.out.println(najdluzszaSciezka(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:

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

R1S7KdTPvBfnY

Przykładowe rozwiązanie zadania:

Linia 1. class Wezel otwórz nawias klamrowy. Linia 2. int klucz średnik. Linia 3. Wezel lewy przecinek prawy średnik. Linia 5. Wezel otwórz nawias okrągły int klucz zamknij nawias okrągły otwórz nawias klamrowy. Linia 6. this kropka klucz znak równości klucz średnik. Linia 7. lewy znak równości prawy znak równości null średnik. Linia 8. zamknij nawias klamrowy. Linia 9. zamknij nawias klamrowy. Linia 11. public class DrzewoBinarne otwórz nawias klamrowy. Linia 12. static int policzOjcowZJednymSynem otwórz nawias okrągły Wezel wezel zamknij nawias okrągły otwórz nawias klamrowy. Linia 13. if otwórz nawias okrągły wezel wykrzyknik znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 14. if otwórz nawias okrągły wezel kropka lewy znak równości znak równości wezel kropka prawy zamknij nawias okrągły otwórz nawias klamrowy. Linia 15. return 0 średnik. Linia 16. zamknij nawias klamrowy else if otwórz nawias okrągły wezel kropka lewy znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 17. return 1 plus policzOjcowZJednymSynem otwórz nawias okrągły wezel kropka prawy zamknij nawias okrągły średnik. Linia 18. zamknij nawias klamrowy else if otwórz nawias okrągły wezel kropka prawy znak równości znak równości null zamknij nawias okrągły otwórz nawias klamrowy. Linia 19. return 1 plus policzOjcowZJednymSynem otwórz nawias okrągły wezel kropka lewy zamknij nawias okrągły średnik. Linia 20. zamknij nawias klamrowy. Linia 21. 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 średnik. Linia 22. zamknij nawias klamrowy. Linia 23. return 0 średnik. Linia 24. zamknij nawias klamrowy. Linia 26. public static void main otwórz nawias okrągły String otwórz nawias kwadratowy zamknij nawias kwadratowy args zamknij nawias okrągły otwórz nawias klamrowy. Linia 27. Wezel korzen znak równości new Wezel otwórz nawias okrągły 7 zamknij nawias okrągły średnik. Linia 29. korzen kropka lewy znak równości new Wezel otwórz nawias okrągły 5 zamknij nawias okrągły średnik. Linia 30. korzen kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 2 zamknij nawias okrągły średnik. Linia 31. korzen kropka lewy kropka prawy znak równości new Wezel otwórz nawias okrągły 6 zamknij nawias okrągły średnik. Linia 32. korzen kropka lewy kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 33. korzen kropka lewy kropka lewy kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 34. korzen kropka lewy kropka lewy kropka lewy kropka lewy kropka lewy znak równości new Wezel otwórz nawias okrągły 1 zamknij nawias okrągły średnik. Linia 35. korzen kropka lewy kropka lewy kropka prawy znak równości new Wezel otwórz nawias okrągły 4 zamknij nawias okrągły średnik. Linia 37. korzen kropka prawy znak równości new Wezel otwórz nawias okrągły 8 zamknij nawias okrągły średnik. Linia 38. korzen kropka prawy kropka prawy znak równości new Wezel otwórz nawias okrągły 10 zamknij nawias okrągły średnik. Linia 39. korzen kropka prawy kropka prawy kropka lewy znak równości new Wezel otwórz nawias okrągły 9 zamknij nawias okrągły średnik. Linia 41. System kropka out kropka println otwórz nawias okrągły policzOjcowZJednymSynem otwórz nawias okrągły korzen zamknij nawias okrągły zamknij nawias okrągły średnik. Linia 42. zamknij nawias klamrowy. Linia 43. zamknij nawias klamrowy.

class Wezel {
	int klucz;
	Wezel lewy, prawy;

	Wezel(int klucz) {
		this.klucz = klucz;
		lewy = prawy = null;
	}
}

public class DrzewoBinarne {
    static int policzOjcowZJednymSynem(Wezel wezel) {
        if (wezel != null) {
            if (wezel.lewy == wezel.prawy) {
                return 0;
            } else if (wezel.lewy == null) {
                return 1 + policzOjcowZJednymSynem(wezel.prawy);
            } else if (wezel.prawy == null) {
                return 1 + policzOjcowZJednymSynem(wezel.lewy);
            }
            return policzOjcowZJednymSynem(wezel.lewy) + policzOjcowZJednymSynem(wezel.prawy);
        }
        return 0;
    }

	public static void main(String[] args) {
		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);

		System.out.println(policzOjcowZJednymSynem(korzen));
	}
}

Prezentacja multimedialna

Dla nauczyciela