Algorithmus, um zu testen, ob ein Binärbaum ein Suchbaum ist, und zählen vollständige Zweige

Question

Ich muss einen rekursiven Algorithmus erstellen, um festzustellen, ob ein binärer Baum ein binärer Suchbaum ist und zählen, wie viele vollständige Zweige es gibt (einen übergeordneten Knoten mit linken und rechten Kinderknoten) mit einer angenommenen globalen Zählvariablen. Dies ist eine Zuordnung für meine Datenstrukturenklasse.

Bisher habe ich

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)
      }
   }
}

Aber ich kann das nicht wirklich herausfinden. Ich weiß, dass dieser Algorithmus das Problem nicht löst, da die Anzahl Null ist, wenn die zweite IF -Anweisung nicht wahr ist.

Könnte mir jemand in diesem Fall helfen?

Answer 1

Wie andere in Kommentaren bereits angegeben haben, haben Sie hier wirklich zwei nicht verwandte Funktionen: Testen, ob der Baum ein Suchbaum ist und die vollständigen Zweige zählen. Wenn die Zuweisung nicht speziell für sie erfordert, würde ich zwei separate Funktionen schreiben.

Lassen Sie uns zuerst die vollständigen Zweige zählen. Das bedeutet, die Knoten zu zählen, die sowohl ein linkes Kind als auch ein rechte Kind haben. Dann müssen Sie den Zähler inkrementieren (count = count + 1) wenn beide T.left und T.right sind nicht null (nicht T.left.data und T.right.data: Die Daten sind für diese Aufgabe keine Rolle).

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

Darüber hinaus müssen Sie den linken Unterbaum auch dann erkunden, wenn der rechte Teilbaum leer ist und Sie den rechten Subtree auch dann erkunden müssen, wenn der linke Teilbaum leer ist. Beobachten Sie also, wo Sie die rekursiven Anrufe einsetzen.

Um zu testen, ob der Baum ein Suchbaum ist, müssen Sie die Datenwerte inspizieren. Sie haben bereits etwas nahe dem richtigen Vergleich; nicht ganz richtig. Schreiben Sie ein paar Beispielbäume mit verschiedenen Formen (Nicht sehr groß, 2 bis 5 Knoten) und führen Sie Ihren Algorithmus darauf aus, um zu sehen, was passiert.

Sie müssen noch einen Ort finden, an dem Sie das Ergebnis der Gültigkeitsprüfung einsetzen müssen. Beobachten Sie erneut, wo Sie die rekursiven Anrufe einsetzen (wenn Sie diesen Teil nur ausführen, gibt es mehrere Lösungen, aber in diesem Stadium machen Sie sich keine Sorgen, wenn Sie nur eines sehen).

Sobald Sie es geschafft haben, beide Funktionen separat zu schreiben und sie an einigen Beispielen getestet zu haben, stellen Sie sie sorgfältig zusammen (falls dies durch die Zuordnung erforderlich).

Answer 2

In solchen Dingen ist es oft einfacher, rückwärts nachzudenken. Überlegen Sie also, was Sie brauchen. Lassen Sie uns aus Ihrer Beschreibung aus:

• Rekursion
• Gültigkeit
• Zählung vollständiger Knoten

Ok, das ist eine ziemlich kurze Liste, das sollte überschaubar sein. Beginnen wir mit einer leeren Methode und ich füge eine Beschreibung hinzu, was passieren soll.

valid_bst () {
}

Jetzt Gültigkeit. Wie überprüfen Sie die Gültigkeit? Im Chat sagten Sie, ein Baum sei gültig "Wenn ... alle linken Kinder weniger als die Eltern sind und die richtigen Kinder größer sind als die Eltern." Ich bin sicher, Sie wollten auch Gleichheit zulassen. Das wäre t.left.value <= t.value <= t.right.value.

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

Aber was ist, wenn eines der Kinder fehlt? Nach dem, was Sie gesagt haben, glaube ich, dass der Knoten immer noch gültig ist, wenn einer (oder beide) fehlt. Fügen wir dies hinzu, um geringfügig umstrukturieren:

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, wir wissen jetzt, ob dieser Knoten gültig ist. Wie überprüfen wir, ob der gesamte Baum gültig ist? Es ist nicht in einem Array, also können wir wahrscheinlich nicht linear darüber schauen/nicht. Ihre Aufgabe gibt die Antwort: Rekursion. Aber wie sammeln wir eine Antwort mit Rekursion? Wir haben Zugriff auf drei Informationen, ob dieser Knoten gültig ist, und das Ergebnis von Aufrufen, in denen gefragt wird, ob die linken und rechten Knoten gültig sind. Offensichtlich ist der Baum nur gültig, wenn alle drei wahr sind.

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.
}

Wenn Sie aufpassen, sagt uns das sogar, was unsere Funktion zurückkehren muss.

Wie integrieren wir die Zählung? Sie sagen, was zählt ("ein übergeordneter Knoten mit linken und rechten Kindern -Knoten"), und das sollte nicht schwer in den tatsächlichen Code übersetzt werden. Überprüfen Sie, ob diese Bedingung erfüllt ist, und erhöhen Sie den Gegensatz angemessen. Denken Sie daran, dass dies an einem Ort sein muss, an dem es jedes Mal erreicht wird, wenn es wahr ist.

Und natürlich habe ich einige Details wie die Recursion -Stopp -Bedingung und Überprüfungen auf NULL ausgelassen.

Answer 3

Meine drei obigen Kommentare sind drei Hinweise auf Probleme mit Ihrem Code.

1. Sofern Sie nicht bereits spezifisch definiert haben, wie ein Vergleichsbetreiber den Knoten -Datentyp verarbeiten sollte, wird es höchstwahrscheinlich nicht das Vergleich von zwei Knoten direkt tun, was Sie wollen. Was Sie wahrscheinlich meinten, war, die in den Knoten gespeicherten Felder zum Beispiel zu vergleichen node1.value < node2.value
2. Im Moment fügen Sie nur dann zur Anzahl hinzu, wenn der dritte if Stimmt, sind Sie sicher, dass Sie das tun möchten? Übrigens möchten Sie möglicherweise überprüfen, ob die Aussage das tut, was Sie wollen.
3. Ich gehe davon aus, dass Sie wahr zurückgeben möchten, wenn der Baum ein gültiger BST ist und ansonsten falsch ist. Dies bedeutet, dass Sie in einem Basisfall immer wahr oder falsch zurückgeben müssen, und Sie sollten auch die Ergebnisse Ihrer rekursiven Anrufe zurückgeben.