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...
- 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
- 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);
}
- 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.
- 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:
- 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.