SHARE
TWEET

Untitled

a guest Nov 14th, 2019 90 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. enum class kolor
  3. {
  4.     czarny, czerwony
  5. };
  6. template  <typename T>
  7. struct wezel {
  8.     wezel() {
  9.         wezel* dziecko = new wezel;
  10.     }
  11.     T dane;
  12.     wezel* wskaznikNaRodzica = nullptr;
  13.     wezel* wskaznikNaPrawegoPotomka = nullptr;
  14.     wezel* wskaznikNaLewegoPotomka = nullptr;
  15.     unsigned int indeks;
  16.  
  17.     kolor color = kolor::czerwony;
  18. };
  19. template< typename T>
  20. struct drzewo {
  21.     wezel* korzen;
  22.     int rozmiar;
  23.     void dodajNowyWezel(T datas) {
  24.         wezel* dziecko = new wezel;
  25.         if (rozmiar == 0) {
  26.             dziecko->wskaznikNaRodzica = nullptr;
  27.             dziecko->wskaznikNaPrawegoPotomka = nullptr;
  28.             dziecko->wskaznikNaLewegoPotomka = nullptr;
  29.             dziecko->indeks = 0;
  30.             korzen = dziecko;
  31.             korzen->color = kolor::czarny;
  32.         }
  33.         else {
  34.             wezel* tymczasowy;
  35.             tymczasowy = korzen;
  36.             while (tymczasowy != nullptr) {
  37.                 if (tymczasowy->dane > datas) {
  38.                     if (tymczasowy->wskaznikNaPrawegoPotomka == nullptr) {
  39.                         tymczasowy->wskaznikNaPrawegoPotomka = dziecko;
  40.                         dziecko->wskaznikNaRodzica = tymczasowy;
  41.                     }
  42.                     else
  43.                     {
  44.                         tymczasowy = tymczasowy->wskaznikNaPrawegoPotomka;
  45.                     }
  46.                 }
  47.                 else {
  48.                     if (tymczasowy->dane > datas) {
  49.                         if (tymczasowy->wskaznikNaLewegoPotomka == nullptr) {
  50.                             tymczasowy->wskaznikNaLewegoPotomka = dziecko;
  51.                             dziecko->wskaznikNaRodzica = tymczasowy;
  52.                         }
  53.                         else
  54.                         {
  55.                             tymczasowy = tymczasowy->wskaznikNaLewegoPotomka;
  56.                         }
  57.                     }
  58.                 }
  59.  
  60.             }
  61.         }
  62.         dziecko->indeks = rozmiar;
  63.         dziecko->dane = datas;
  64.         rozmiar++;
  65.  
  66.     }
  67.     void sprawdzKolory(wezel* ostatni) {
  68.         while (ostatni->wskaznikNaRodzica->color == ostatni->color) {
  69.             wezel* wujek = nullptr;
  70.             wezel* dziadek = ostatni->wskaznikNaRodzica->wskaznikNaRodzica;
  71.             if (ostatni->wskaznikNaRodzica == dziadek->wskaznikNaLewegoPotomka) {
  72.                 if (dziadek->wskaznikNaPrawegoPotomka) {
  73.                     wujek = dziadek->wskaznikNaPrawegoPotomka;
  74.                 }
  75.                 if (wujek->color == kolor::czerwony) {
  76.                     ostatni->wskaznikNaRodzica->color = kolor::czarny;
  77.                     wujek->color = kolor::czarny;
  78.                     dziadek->color = kolor::czerwony;
  79.                     if (dziadek->dane != korzen->dane) {
  80.                         ostatni = dziadek;
  81.                     }
  82.                     else {
  83.                         break;
  84.                     }
  85.                 }
  86.                 if (ostatni == dziadek->wskaznikNaLewegoPotomka->wskaznikNaPrawegoPotomka) {
  87.                     RotacjaLewa(ostatni->wskaznikNaRodzica, ostatni);
  88.                 }
  89.                 else {
  90.                     ostatni->wskaznikNaRodzica->color = kolor::czarny;
  91.                     dziadek->color = kolor::czerwony;
  92.                     RotacjaPrawa(dziadek->wskaznikNaRodzica, dziadek);
  93.                     if (dziadek->dane != korzen->dane) {
  94.                         ostatni = dziadek;
  95.                     }
  96.                     /*else {
  97.                         break;
  98.                     }*/
  99.                 }
  100.             }
  101.             else {
  102.                 if (dziadek->wskaznikNaLewegoPotomka) {
  103.                     wujek = dziadek->wskaznikNaLewegoPotomka;
  104.                 }
  105.                 if (wujek->color == kolor::czerwony) {
  106.                     ostatni->wskaznikNaRodzica->color = kolor::czarny;
  107.                     wujek->color = kolor::czarny;
  108.                     dziadek->color = kolor::czerwony;
  109.                     if (dziadek->dane != korzen->dane) {
  110.                         ostatni = dziadek;
  111.                     }
  112.                     /*else {
  113.                         break;
  114.                     }*/
  115.                 }
  116.                 if (ostatni == dziadek->wskaznikNaPrawegoPotomka->wskaznikNaLewegoPotomka) {
  117.                     RotacjaPrawa(ostatni->wskaznikNaRodzica, ostatni);
  118.                 }
  119.                 else {
  120.                     ostatni->wskaznikNaRodzica->color = kolor::czarny;
  121.                     dziadek->color = kolor::czerwony;
  122.                     RotacjaLewa(dziadek->wskaznikNaRodzica, dziadek);
  123.                     if (dziadek->dane != korzen->dane) {
  124.                         ostatni = dziadek;
  125.                     }
  126.                     //else { break; }
  127.                 }
  128.             }
  129.         }
  130.         korzen->color = kolor::czarny;
  131.     }
  132.     void RotacjaPrawa(wezel* naRodzica, wezel* naDziecko) {
  133.         //Rodzicem elementu naRodzica staje się element naDziecko,
  134.         naRodzica->wskaznikNaRodzica = naDziecko;
  135.  
  136.         //lewy syn elementu naDziecko staje się prawym synem elementu naRodzica.
  137.         naRodzica->wskaznikNaPrawegoPotomka = naDziecko->wskaznikNaLewegoPotomka;
  138.  
  139.         //lewym dzieckiem elementu naDziecko staje się element naRodzica.
  140.         naDziecko->wskaznikNaLewegoPotomka = naRodzica;
  141.     }
  142.     void RotacjaLewa(wezel* naRodzica, wezel* naDziecko) {
  143.         naRodzica->wskaznikNaRodzica = naDziecko;
  144.         naRodzica->wskaznikNaLewegoPotomka = naDziecko->wskaznikNaPrawegoPotomka;
  145.         naDziecko->wskaznikNaPrawegoPotomka = naRodzica;
  146.     }
  147.     wezel* znajdzDane(T datas) {
  148.         wezel* cos = korzen;
  149.         while (cos) {
  150.             if (cos->dane == datas) {
  151.                 return cos;
  152.             }
  153.             if (datas > cos->dane) {
  154.                 cos = cos->wskaznikNaPrawegoPotomka;
  155.             }
  156.             else {
  157.                 cos = cos->wskaznikNaLewegoPotomka;
  158.             }
  159.             return nullptr;
  160.         }
  161.     }
  162.     void wyczyscDrzewo() {
  163.         wezel* kasownik = korzen;
  164.         wyczyscDrzewoRek(kasownik);
  165.     }
  166.     void wyczyscDrzewoRek(wezel* kasownik) {
  167.         if (kasownik == nullptr) {
  168.             return;
  169.         }
  170.         else {
  171.             wyczyscDrzewoRek(kasownik->wskaznikNaLewegoPotomka);
  172.             wyczyscDrzewoRek(kasownik->wskaznikNaPrawegoPotomka);
  173.             delete kasownik;
  174.         }
  175.     }
  176.     //przechodzenie przez wezły
  177.     void InOrder(wezel* drzewo) {
  178.         InOrder(drzewo->wskaznikNaLewegoPotomka);
  179.         std::cout << drzewo->dane << ' ';
  180.         InOrder(drzewo->wskaznikNaPrawegoPotomka);
  181.     }
  182.     //PreOrder służy do kopiowania drzewa
  183.     void PreOrder(wezel* drzewo) {
  184.         std::cout << drzewo->dane << ' ';
  185.         PreOrder(drzewo->wskaznikNaLewegoPotomka);
  186.         PreOrder(drzewo->wskaznikNaPrawegoPotomka);
  187.     }
  188.     void wysokoscDrzewa() {
  189.         int wysokosc = 0;
  190.         wysokoscLiczenie(korzen);
  191.         wysokosc++;
  192.     }
  193.     void wysokoscLiczenie(wezel* drzewo) {
  194.         InOrder(drzewo->wskaznikNaLewegoPotomka);
  195.         std::cout << drzewo->dane << ' ';
  196.         InOrder(drzewo->wskaznikNaPrawegoPotomka);
  197.     }
  198. };
  199. int main() {
  200.     drzewo CzerwonoCzarne;
  201.  
  202. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top