Algorytm sprawdzający, czy drzewo binarne jest drzewem wyszukiwania i zlicza pełne gałęzie

Muszę utworzyć algorytm rekurencyjny, aby sprawdzić, czy drzewo binarne jest drzewem wyszukiwania binarnego, a także policzyć, ile jest pełnych gałęzi (węzeł nadrzędny z lewym i prawym węzłem podrzędnym) z założoną globalną zmienną zliczającą. To zadanie dla mojej klasy struktur danych.

Do tej pory mam

void BST(tree T) {
   if (T == null) return
   if ( T.left and T.right) {
      if (T.left.data < T.data or T.right.data > T.data) {
        count = count + 1
        BST(T.left)
        BST(T.right)
      }
   }
}

Ale tak naprawdę nie mogę tego rozgryźć. Wiem, że ten algorytm nie rozwiąże problemu, ponieważ liczba będzie wynosić zero, jeśli druga instrukcja if nie jest prawdziwa.

Czy ktoś mógłby mi pomóc w tej sprawie?

Jak już inni wskazali w komentarzach, naprawdę masz tutaj dwie niezwiązane funkcje: sprawdzanie, czy drzewo jest drzewem wyszukiwania i liczenie pełnych gałęzi. O ile zadanie tego nie wymaga, napisałbym dwie osobne funkcje.

Zobaczmy najpierw liczenie kompletnych gałęzi. Oznacza to zliczanie węzłów, które mają zarówno lewe, jak i prawe dziecko. Następnie trzeba zwiększyć licznik ( count = count + 1), gdy oba T.lefti T.rightsą niezerowe (nie T.left.datai T.right.data: dane nie ma znaczenia dla tego zadania).

if (T.left and T.right) {
    count = count + 1

Ponadto należy zbadać lewe poddrzewo, nawet jeśli prawe poddrzewo jest puste, i zbadać prawe poddrzewo, nawet jeśli lewe poddrzewo jest puste. Uważaj więc, gdzie wykonujesz połączenia rekurencyjne.

Aby sprawdzić, czy drzewo jest drzewem wyszukiwania, należy sprawdzić wartości danych. Masz już coś zbliżonego do właściwego porównania; nie do końca. Napisz kilka przykładowych drzew o różnych kształtach (niezbyt duże, od 2 do 5 węzłów) i uruchom na nich swój algorytm, aby zobaczyć, co się stanie.

Nadal musisz znaleźć miejsce do umieszczenia wyniku kontroli ważności. Ponownie, patrz, gdzie umieszczasz rekurencyjne połączenia (jeśli wykonasz tylko tę część, istnieje kilka rozwiązań, ale na tym etapie nie martw się, jeśli zobaczysz tylko jedno).

Wreszcie, gdy uda ci się napisać obie funkcje osobno i przetestujesz je na kilku przykładach, ułóż je ostrożnie (jeśli wymaga tego zadanie).

W takich przypadkach często łatwiej jest myśleć wstecz, więc najpierw zastanów się, czego potrzebujesz. Z opisu opiszmy je:

• Rekurencja
• Ważność
• Liczba kompletnych węzłów

OK, to dość krótka lista, powinna być zarządzalna. Zacznijmy od pustej metody i dodam opis tego, co powinno się dziać.

valid_bst () {
}

Teraz ważność. Jak sprawdzasz ważność? Na czacie powiedziałeś, że drzewo jest ważne „jeśli ... wszystkie lewe dzieci są mniejsze niż rodzic, a prawe dzieci są większe niż rodzic”. Jestem pewien, że chciałeś również pozwolić na równość. To by było t.left.value <= t.value <= t.right.value.

valid_bst () {
    This node is valid if t.left.value <= t.value <= t.right.value
}

Ale co jeśli jedno z dzieci zaginie? Z tego, co powiedziałeś, uważam, że wiesz, że węzeł jest nadal ważny, jeśli brakuje jednego (lub obu). Dodajmy to, nieco restrukturyzując:

valid_bst () {
    This node is valid to the left if 
        there is no left child or 
        it is no greater than the current node.
    This node is valid to the right if 
        there is no right child or 
        it is no less than the current node.
    This node is valid overall if it is valid to the left and right.
}

OK, teraz wiemy, czy ten węzeł jest prawidłowy. Jak sprawdzamy, czy całe drzewo jest prawidłowe? Nie ma go w tablicy, więc prawdopodobnie nie możemy / nie chcemy zapętlać go liniowo. Twoje zadanie daje odpowiedź: rekurencja. Ale w jaki sposób gromadzimy odpowiedź za pomocą rekurencji? Mamy dostęp do trzech informacji, czy ten węzeł jest prawidłowy, oraz wyników połączeń z pytaniem, czy lewy i prawy węzeł są prawidłowe. Oczywiście drzewo jest ważne tylko wtedy, gdy wszystkie trzy są prawdziwe.

valid_bst () {
    This node is valid to the left if 
        there is no left child or 
        it is no greater than the current node.
    This node is valid to the right if 
        there is no right child or 
        it is no less than the current node.
    This node is valid overall if it is valid to the left and right.
    Is the left child valid?
    Is the right child valid?
    This tree is only valid if this node and both its children are.
}

Jeśli zwracasz uwagę, to nawet mówi nam, co nasza funkcja musi zwrócić.

Jak teraz zintegrować liczenie? Mówisz, co się liczy („węzeł nadrzędny z lewym i prawym węzłem podrzędnym”) i nie powinno to być trudne do przetłumaczenia na rzeczywisty kod. Sprawdź, czy ten warunek jest spełniony, i odpowiednio zwiększ licznik. Pamiętaj tylko, że musi to być gdzieś, gdzie będzie to możliwe, za każdym razem, gdy będzie to prawdą.

I oczywiście pominąłem niektóre szczegóły, takie jak warunek zatrzymania rekurencji i sprawdzanie wartości zerowej.

Moje trzy komentarze powyżej to trzy wskazówki dotyczące problemów z twoim kodem.

1. O ile wcześniej nie zdefiniowałeś, w jaki sposób operator porównania powinien obsługiwać typ danych węzła, najprawdopodobniej bezpośrednie porównanie dwóch węzłów nie zrobi tego, co chcesz. To, co prawdopodobnie miałeś na myśli, to na przykład porównanie pól przechowywanych w węzłachnode1.value < node2.value
2. w tej chwili dodajesz do liczby, jeśli trzecia ifjest prawdziwa, czy jesteś pewien, że właśnie to chciałeś zrobić? Nawiasem mówiąc, możesz chcieć dokładnie sprawdzić, czy instrukcja if robi to, co chcesz.
3. Zakładam, że chcesz zwrócić true, jeśli drzewo jest poprawnym BST, a false w przeciwnym razie. Co oznacza, że ​​zawsze musisz zwrócić prawdę lub fałsz w przypadku podstawowym i powinieneś również zwracać wyniki swoich połączeń rekurencyjnych.