Drzewo binarne uporządkowane przechowujące ciągi znaków (typ string) – demonstracja. Doprawidłowego przeprowadzenia sprawdzenia działania programu należy przygotować plik zawierający przykładowe ciągi znaków w osobnych wierszach.

main.cpp

/**
 * \file main.cpp
 * \brief Program demonstrujący działanie drzewa uporządkowanego (binarnego)
 * \author Rafał Wileczek (na podstawie podręcznika do informatyki rozszerzonej)
 * \version 1.0
 * \date 2018
 *
 * Program jest modyfikacją przykładu z podręcznika do informatyki rozszerzonej – zamiast
 * liczb całkowitych porządkowane są napisy (ciągi znaków)
 *
 */

#include <iostream>
#include <fstream>
#include <cstdlib>

using namespace std;

/**
 * \struct SWezel
 * \brief Struktura przechowująca węzeł drzewa
 *
 * Każdy nowo utworzony węzeł (liść) drzewa będzie elementem typu strukturalnego SWezel.
 */
struct SWezel
{
    string pole;        //!< pole przechowujące zasadnicze dane elementu drzewa (napis)
    SWezel *lewySyn;    //!< wskaźnik na lewe odgałęzienie drzewa
    SWezel *prawySyn;   //!< wskaźnik na prawe odgałęzienie drzewa
};

SWezel *korzen = NULL; //!< korzeń drzewa (wskaźnik na pierwszy element)

ifstream plik; //!< plik z danymi wejściowymi (tutaj nazwy kilku miast umieszczone w osobnych wierszach)

/**
 * \brief Utworzenie nowego węzła drzewa
 *
 * \param dane napis (ciąg znaków) do wprowadzenia do drzewa
 * \return utworzony węzeł drzewa
 *
 * Funkcja tworzy nowy węzeł drzewa i zwraca wskaźnik na utworzony węzeł.
 *
 * \see dodajWezel()
 */
SWezel* stworzNowyWezel(string dane)
{
    SWezel* nowyWezel = new SWezel;
    nowyWezel->lewySyn = NULL;
    nowyWezel->prawySyn = NULL;
    nowyWezel->pole = dane;

    return nowyWezel;
}

/**
 * \brief Dodawanie nowego węzła do drzewa
 *
 * \param wezelPoczatkowy węzeł, do którego dołączany jest nowy, utworzony w tej funkcji
 * \param dane napis do umieszczenia w nowym węźle
 *
 * Funkcja dodająca rekurencyjnie nowy element do drzewa zgodnie z ideą drzewa uporządkowanego.
 *
 * \see stworzNowyWezel()
 */
void dodajWezel(SWezel *wezelPoczatkowy, string dane)
{
    if(korzen == NULL) // gdy drzewo jest puste, korzen jest zmienna globalna przechowujaca korzen tworzonego drzewa
    {
        korzen = stworzNowyWezel(dane); // tworzenie pierwszego wezla w drzewie
    }
    else // jezeli drzewo niepuste
    {
        // jezeli nowa liczba jest mniejsza od wartosci w wezle, dodaj do lewego podrzewa
        if(dane < wezelPoczatkowy->pole)
        {
            // jezeli lewy syn nie jest pusty wywolaj rekurenyjnie dodawanie do lewego podrzewa
            if(wezelPoczatkowy->lewySyn != NULL)
            {
                dodajWezel(wezelPoczatkowy->lewySyn, dane);
            }
            // jezeli lewe podrzewo nie istnieje, to niech lewy syn wskazuje na nowo utworzony wezel z nowa wartoscia
            else
            {
                wezelPoczatkowy->lewySyn = stworzNowyWezel(dane);
            }
        }
        // jezeli nowa liczba jest rowna lub wieksza od wartosci w wezle, dodaj do prawego podrzewa
        else
        {
            // jezeli prawy syn nie jest pusty wywolaj rekurenyjnie dodawanie do prawego podrzewa
            if(wezelPoczatkowy->prawySyn != NULL)
            {
                dodajWezel(wezelPoczatkowy->prawySyn, dane);
            }
            // jezeli prawe podrzewo nie istnieje, to niech prawy syn wskazuje na nowo utworzony wezel z nowa wartoscia
            else
            {
                wezelPoczatkowy->prawySyn = stworzNowyWezel(dane);
            }
        }
    }
}

/**
 * \brief Wypisywanie zawartości drzewa niemalejąco
 *
 * \param wezelPoczatkowy węzeł, od którego rozpoczyna się wypisywanie zawartości drzewa
 *
 * Funkcja wypisująca na standardowym wyjściu (konsola) zawartość drzewa binarnego
 * niemalejąco.
 *
 * \see wypiszDrzewoMalejaco()
 */
void wypiszDrzewoNiemalejaco(SWezel *wezelPoczatkowy)
{
     // jezeli wezel nie jest pusty
     if(wezelPoczatkowy != NULL)
     {
         // rekurencyjnie wypisz lewe poddrzewo
         wypiszDrzewoNiemalejaco(wezelPoczatkowy->lewySyn);
         // wypisz wartosc aktualnego wezla
         cout << wezelPoczatkowy->pole << endl;
         // rekurencyjnie wypisz prawe poddrzewo
         wypiszDrzewoNiemalejaco(wezelPoczatkowy->prawySyn);
     }
}

/**
 * \brief Wypisywanie zawartości drzewa malejąco
 *
 * \param wezelPoczatkowy węzeł, od którego rozpoczyna się wypisywanie zawartości drzewa
 *
 * Funkcja wypisująca na standardowym wyjściu (konsola) zawartość drzewa binarnego
 * malejąco.
 *
 * \see wypiszDrzewoNiemalejaco()
 */
void wypiszDrzewoMalejaco(SWezel *wezelPoczatkowy)
{
     // jezeli wezel nie jest pusty
     if(wezelPoczatkowy != NULL)
     {
         // rekurencyjnie wypisz lewe poddrzewo
         wypiszDrzewoMalejaco(wezelPoczatkowy->prawySyn);
         // wypisz wartosc aktualnego wezla
         cout << wezelPoczatkowy->pole << endl;
         // rekurencyjnie wypisz prawe poddrzewo
         wypiszDrzewoMalejaco(wezelPoczatkowy->lewySyn);
     }
}

/**
 *  \brief Punkt startowy programu
 *
 *  Program demonstruje wykorzystanie struktury drzewa binarnego uporządkowanego do
 *  przechowywania danych w sposób ułatwiający ich wypisanie/wyprowadzenie w sposób
 *  dowolnie posortowany.
 *  Problem stanowią polskie znaki diakrytyczne (prawdopodobnie jest to związane z działaniem
 *  przeciążonego operatora relacji /porównania/).
 *
 */
int main()
{
    cout << "Wczytanie napisów z pliku: " << endl;

    plik.open("dane_wejsciowe", ifstream::in);
    if (plik.is_open()) {
        int i = 1;
        while (plik.good()) {
            string wiersz = "";
            plik >> wiersz;
            cout << i << ".\t" << wiersz << endl;
            dodajWezel(korzen, wiersz);
            i++;
        }
        plik.close();
    } else {
        cout << "Błąd otwarcia pliku z danymi." << endl;
        return 0;
    }

    cout<<"\n\nPosortowane elemnty z drzewa (niemalejaco): " << endl;
    wypiszDrzewoNiemalejaco(korzen); // wypisz elemnety drzewa w posortowanej kolejnosci
    cout<<"\n\nPosortowane elemnty z drzewa (malejaco): " << endl;
    wypiszDrzewoMalejaco(korzen); // wypisz elemnety drzewa w posortowanej kolejnosci

    delete korzen;

    return 0;
}