Drzewo BST, drukowanie elementów w kolejności algorytm

Odpowiedz Nowy wątek
2015-02-09 13:19
0

Mam problem ze zrozumieniem algorytmu który drukuje w kolejności wszystkie elementy drzewa BST. Problem dość zawiły, więc próbowałem wytłumaczyć o co mi chodzi dość skrupulatnie.

Mam taki oto kod do drukowania wszystkich elementów w kolejności rosnącej, poczynając od klasy BST:

class BST 
{
   private: 
              struct Node{ 
                              int key; 
                              Node *right, *left; 
                              }; 
              Node *root; 
              void drukujDrzewoPrivate(Node *ptr); 

  public: 
              void drukujDrzewo(); 
}; 

Definicja:


void BST::drukujDrzewo() 
{
   drukujDrzewoPrivate(root); 
} 

void BST::drukujDrzewoPrivate(int key, Node *ptr) 
{
   if(root != NULL)  
   { 
      if(ptr->left != NULL) 
      { 
         PrintInOrder(ptr->left); 
      } 
      std::cout << ptr->key; 

     if(ptr->right != NULL) 
         PrintInOrder(ptr->right); 
    } 
    else 
       std::cout << "Drzewo jest puste, brak korzenia!\n"; 
} 

Chcę by ktoś mi wytłumaczył w jaki sposób funkcja drukujDrzewoPrywatnie (nazwana tak bo operuje na polach prywatnych *Node ptr), za każdym razem wraca z powrotem do korzenia.

Jakby ktoś mógłby wytłumaczyć na czym polega mój błąd, pokazałem to obrazowo na rysunkach w jaki sposób według mnie działa ten algorytm - tu pewnie w czymś się mylę. A więc...

  1. Na początku sprawdzamy czy korzeń nie jest pusty, jeśli coś w nim jest, tj. poniższy warunek jest spełniony:

if(root!=NULL) 

to idziemy do punktu 2. Obrazek pierwszy z załącznika

  1. Sprawdzamy teraz czy nasz korzeń ma "lewe dziecko" (element mniejszy od niego), jeśli wskaźnik nie jest NULL to mamy lewe dziecko i rekursywnie wywołujemy dla niego funkcję drukujDrzewoPrivate(ptr->left).
    Obrazek drugi z załącznika

if(ptr->left != NULL) 
{ 
   drukujDrzewoPrivate(ptr->left); 
}
  1. Następnie funkcja drukujDrzewoPrivate() rozpoczyna się od nowa biorąc za swój korzeń poddrzewo zaczynające się od 55.
    Obrazek 3 z załącznika

Sprawdza czy lewe dziecko dla liścia z wartością 55 ma wartość NULL, zgodnie z:


if(ptr->left != NULL) 
{ 
   drukujDrzewoPrivate(ptr->left); 
}

Jeśli ptr->left != NULL, znaczy że ma jakieś "lewe dziecko" i wywołuje znów rekursywnie drukujDrzewoPrivate, tym razem dla tego lewego dziecka czyli: 45.

  1. Funkcja znów zaczyna od korzenia poddrzewa w którym korzeń ma wartość 45. Tym razem, poddrzewo nie ma już żadnego "lewego dziecka".

Obrazek 4 z załącznika

Więc zgodnie z funkcją drukujDrzewoPrivate() jeśli wskaźnik na "lewe dziecko" wskazuje na NULL i poniższy warunek nie został spełniony:

if(ptr->left != NULL)

to funkcja idzie dalej, czyli przechodzi do

 cout << ptr->key 

drukując 45, omija pozostałe linie bo prawego dziecka liść z wartością 45 i tak nie ma i teraz pojawia się pytanie, w jaki sposób funkcja sama ponownie się wywołuje by dojść do 55 skoro po tym jak lewe dziecko 45 wskazywało na NULL warunek ptr->left != NULL nie został spełniony, sterowanie przeszło do linijki w której wydrukowaliśmy wartość tego klucza i do warunków których wartość klucza nie została spełniona (bo prawego dziecka też liśc z 45 nie ma), sterowanie omineło te linijki i magicznie zawróciło na początek funkcji.

Pytanie: jak funkcja znów mogła się "zawrócić" do początku, skoro po tym jak warunek if(ptr->left!=NULL) nie został spełniony ominęła linijkę w której sama się wywołuje, a potem przechodzi przez linijki z warunkami których i tak dla pierwszego argumentu (45) nie spełnia.

Problem polega na tym że jak zmienię klamry w funkcji drukujDrzewoPrivate() na takie 2 sposoby, to funkcja nie drukuje poprawnie liczb:(na grubo to co zostało zmienione)


if(root != NULL)  
   { 
      if(ptr->left != NULL) 
      { 
         drukujDrzewoPrivate(ptr->left); 
      }
     ** else**
      **{**
         std::cout << ptr->key; 
       **}**
     if(ptr->right != NULL) 
         drukujDrzewoPrivate(ptr->right); 
    }  

lub


if(root != NULL)  
   { 
      if(ptr->left != NULL) 
      { 
         drukujDrzewoPrivate(ptr->left); 
        ** std::cout << ptr->key; ** // w jednej klamerce po spełnieniu warunku ptr->left != NULL
      }
     if(ptr->right != NULL) 
         drukujDrzewoPrivate(ptr->right); 
    }  

Czy mam rozumieć że ten cout wywołuje się gdy:

  1. Sterowanie funkcji przejdzie przez warunek ptr->left != NULL i nie zostanie on spełniony, następnie sterowanie przejdzie do cout i potem do tych warunków poniżej ?

I pytanie elementarne, dla liścia z wartością 45 warunek ptr->left będzie zwracał NULL, czyli nie zostanie spełniony, przejdzie do cout, by nie spełnić także warunku z ptr->right != NULL, a pętla mimo pominięcia drukujDrzewoPrivate() znów się wywoła dla 55.

edytowany 2x, ostatnio: ond3__, 2015-02-09 13:24

Pozostało 580 znaków

2015-02-09 13:34
0

Najlepiej to będzie jak odpalisz debugger i przejdziesz krok po kroku. Ale opisując "na gębę" to wygląda tak:
odwiedź 65 jest lewy -> idź odwiedź 55 jest lewy -> idź odwiedź 45 nie ma lewego wypisz 45 nie ma prawego wypisz 55 jest prawy -> idź odwiedź 60 nie ma lewego wypisz 60 nie ma prawego wypisz 65 jest prawy -> idź odwiedź 76 ....

Teraz podstaw za odwiedź funkcję PrintInOrder, a za wypisz cout.
Podstawianie za odwiedź drukujDrzewoPrivate jest błędne.

edytowany 2x, ostatnio: twonek, 2015-02-09 13:37

Pozostało 580 znaków

2015-02-09 13:47
0

@twonek: no tak, wiem że tak ten algorytm działa bo analizowałem to w jaki sposób drukuje poprawnie te litery. Problem polega na tym że nie wiem jakim cudem wytłumaczyć to że po tym jak:

wypisz 45

przechodzi do:

nie ma prawego 
**wypisz 55**

Skoro warunek: if(ptr->right != NULL), nie został spełniony, bo dla 45 ptr->right jest faktycznie NULL to jak mogła zostac wywołana ponownie funkcja drukujDrzewoPrivate() ?

Nie wiem czy dobrze to pojmuje, ale skoro nie ma prawego dla 45, to ptr->right == NULL i sterowanie wychodzi z funkcji, bo żaden z warunków nie został spełniony a funkcja mimo to znów się wywołuje.

Tak jakby na końcu zostało dodane:


.
.
.
if(ptr->right != NULL) // ten warunek i tak nie spełnia 45, więc funkcja poniżej drukujDrzewoPrivate nie ma prawa być wywołana 
{
   drukujDrzewoPrivate(ptr->right); 
} 

// tu jest pusto, a jest tak jak gdyby było dodane: drukujDrzewoPrivate(ptr->root); 

Pozostało 580 znaków

2015-02-09 13:53

Po pierwsze: drukujDrzewoPrivate (połączenie polskiego i angielskiego jest słabe) jest wywołane tylko raz. Przechodzenie po drzewie realizuje PrintInOrder.
Teraz wyobraź sobie, że PrintInOrder wchodzi do węzła 55. Potem wchodzi do węzła 45 (ale jeszcze nie skończyło obsłużyć 55). Wychodzi z węzła 45 i kontynuuje w węźle 55. Po wyjściu z 55 kontynuuje w 65, bo było tam zanim weszło do 55.

@twonek: fakt, przepraszam że zmieniałem nazwy metod, ale korzystałem z angielskiej implementacji. To wytłumaczenie do mnie trafia i jest bardzo sensnowne :), dzięki - ond3__ 2015-02-09 14:13

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0