Advertisement
Guest User

Untitled

a guest
Nov 20th, 2019
206
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.21 KB | None | 0 0
  1.     bool szukajPętli(wezel<T>* korzen) {
  2.         std::queue<wezel<T>*> kolejkaWęzłówDoOdwiedzenia;
  3.         std::unordered_set<wezel<T>*> zbiórOdwiedzonychWęzłów;
  4.         kolejkaWęzłówDoOdwiedzenia.emplace(korzen);
  5.  
  6.  
  7.         while (kolejkaWęzłówDoOdwiedzenia.empty() != true) {
  8.             auto analizowanyWęzęł = kolejkaWęzłówDoOdwiedzenia.front();
  9.             kolejkaWęzłówDoOdwiedzenia.pop();
  10.  
  11.             if (zbiórOdwiedzonychWęzłów.count(analizowanyWęzęł) != 0) {
  12.                 // węzęł który sprawdzam, już był wcześniej odwiedzony
  13.                 std::cout << "Znaleziono pętlę w drzewie" << std::endl;
  14.                 return true;
  15.             }
  16.  
  17.             zbiórOdwiedzonychWęzłów.emplace(analizowanyWęzęł);
  18.  
  19.             if (analizowanyWęzęł->wskaznikNaLewegoPotomka != nullptr) {
  20.                 kolejkaWęzłówDoOdwiedzenia.emplace(analizowanyWęzęł->wskaznikNaLewegoPotomka);
  21.             }
  22.             if (analizowanyWęzęł->wskaznikNaPrawegoPotomka != nullptr) {
  23.                 kolejkaWęzłówDoOdwiedzenia.emplace(analizowanyWęzęł->wskaznikNaPrawegoPotomka);
  24.             }
  25.         }
  26.  
  27.         if (zbiórOdwiedzonychWęzłów.size() != this->rozmiar) {
  28.             std::cout << "Odwiedzono inną liczbę węzłów niż rozmiar drzewa" << std::endl;
  29.         }
  30.         std::cout << "Brak pętli w drzewie" << std::endl;
  31.         return false;
  32.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement