Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- bool szukajPętli(wezel<T>* korzen) {
- std::queue<wezel<T>*> kolejkaWęzłówDoOdwiedzenia;
- std::unordered_set<wezel<T>*> zbiórOdwiedzonychWęzłów;
- kolejkaWęzłówDoOdwiedzenia.emplace(korzen);
- while (kolejkaWęzłówDoOdwiedzenia.empty() != true) {
- auto analizowanyWęzęł = kolejkaWęzłówDoOdwiedzenia.front();
- kolejkaWęzłówDoOdwiedzenia.pop();
- if (zbiórOdwiedzonychWęzłów.count(analizowanyWęzęł) != 0) {
- // węzęł który sprawdzam, już był wcześniej odwiedzony
- std::cout << "Znaleziono pętlę w drzewie" << std::endl;
- return true;
- }
- zbiórOdwiedzonychWęzłów.emplace(analizowanyWęzęł);
- if (analizowanyWęzęł->wskaznikNaLewegoPotomka != nullptr) {
- kolejkaWęzłówDoOdwiedzenia.emplace(analizowanyWęzęł->wskaznikNaLewegoPotomka);
- }
- if (analizowanyWęzęł->wskaznikNaPrawegoPotomka != nullptr) {
- kolejkaWęzłówDoOdwiedzenia.emplace(analizowanyWęzęł->wskaznikNaPrawegoPotomka);
- }
- }
- if (zbiórOdwiedzonychWęzłów.size() != this->rozmiar) {
- std::cout << "Odwiedzono inną liczbę węzłów niż rozmiar drzewa" << std::endl;
- }
- std::cout << "Brak pętli w drzewie" << std::endl;
- return false;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement