import random

# Klasa reprezentująca węzeł drzewa
class SWezel:
    def __init__(self, dana):
        self.dana = dana
        self.lewy_syn = None
        self.prawy_syn = None

korzen = None  # Tworzymy korzeń drzewa

# Funkcja dodająca nowy element do drzewa, korzystająca z rekurencji
def dodaj_wezel(wezel_poczatkowy, liczba):
    global korzen # korzeń jest zmienną globalną przechowującą korzeń tworzonego drzewa
    if korzen is None:  # Gdy drzewo jest puste
        nowy_wezel = SWezel(liczba)
        korzen = nowy_wezel  # Tworzenie pierwszego węzła w drzewie
    else:  # Jeżeli drzewo niepuste
        # Jeżeli nowa liczba mniejsza od wartości w węźle dodaj do lewego poddrzewa
        if liczba < wezel_poczatkowy.dana:
            # Jeżeli lewy syn nie jest pusty wywołaj rekurencyjnie dodawanie do lewego poddrzewa
            if wezel_poczatkowy.lewy_syn is not None:
                dodaj_wezel(wezel_poczatkowy.lewy_syn, liczba)
            # Jeżeli lewe poddrzewo nie istnieje, to niech lewy syn wskazuje na nowo utworzony węzeł z nową wartością
            else:
                wezel = SWezel(liczba)
                wezel_poczatkowy.lewy_syn = wezel
        # Jeżeli nowa liczba równa lub większa od wartości w węźle dodaj do prawego poddrzewa
        else:
            # Jeżeli prawy syn nie jest pusty wywołaj rekurencyjnie dodawanie do prawego poddrzewa
            if wezel_poczatkowy.prawy_syn is not None:
                dodaj_wezel(wezel_poczatkowy.prawy_syn, liczba)
            # Jeżeli prawe poddrzewo nie istnieje, to niech prawy syn wskazuje na nowo utworzony węzeł z nową wartością
            else:
                wezel1 = SWezel(liczba)
                wezel_poczatkowy.prawy_syn = wezel1

# Funkcja rekurencyjnie przeglądająca drzewo
def wypisz_drzewo_niemalejaco(wezel_poczatkowy):
    # Jeżeli węzeł nie jest pusty
    if wezel_poczatkowy is not None:
        # Rekurencyjnie wypisz lewe poddrzewo
        wypisz_drzewo_niemalejaco(wezel_poczatkowy.lewy_syn)
        # Wypisz wartość aktualnego węzła
        print(wezel_poczatkowy.dana, end=", ")
        # Rekurencyjnie wypisz prawe poddrzewo
        wypisz_drzewo_niemalejaco(wezel_poczatkowy.prawy_syn)

print("Wygenerowane losowe liczby: ", end="")

# Wygeneruj 10 losowych liczb
for _ in range(10):
    liczba = random.randint(1, 100)  # Liczby z przedziału <1, 100>
    print(liczba, end=", ")
    dodaj_wezel(korzen, liczba)  # Dodawaj wygenerowane liczby do drzewa

print("\n\nPosortowane elementy z drzewa: ", end="")
wypisz_drzewo_niemalejaco(korzen)  # Wypisz elementy drzewa w osortowanej kolejności

korzen = None  # W Pythonie, garbage collection zajmie się usunięciem

input("\n\nNaciśnij ENTER, aby kontynuować...")