Ich muss einen rekursiven Algorithmus erstellen, um zu sehen, ob ein Binärbaum ein binärer Suchbaum ist, und um zu zählen, wie viele vollständige Zweige vorhanden sind (ein übergeordneter Knoten mit sowohl linken als auch rechten untergeordneten Knoten) mit einer angenommenen globalen Zählvariablen. Dies ist eine Zuordnung für meine Datenstrukturklasse.
Soweit 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ösen wird, da die Anzahl Null ist, wenn die zweite if-Anweisung nicht wahr ist.
Könnte mir jemand dabei helfen?
algorithms
recursion
trees
OghmaOsiris
quelle
quelle
<
auf Knoten definiert?true
oderfalse
?Antworten:
Wie andere bereits in Kommentaren angegeben haben, haben Sie hier wirklich zwei nicht miteinander verbundene Funktionen: Testen, ob der Baum ein Suchbaum ist, und Zählen der vollständigen Zweige. Wenn die Aufgabe dies nicht ausdrücklich erfordert, würde ich zwei separate Funktionen schreiben.
Lassen Sie uns zuerst sehen, wie die gesamten Zweige gezählt werden. Das bedeutet, die Knoten zu zählen, die sowohl ein linkes als auch ein rechtes Kind haben. Dann müssen Sie den Zähler (
count = count + 1
) erhöhen, wenn beideT.left
undT.right
nicht null sind (nichtT.left.data
undT.right.data
: Die Daten spielen für diese Aufgabe keine Rolle).Darüber hinaus müssen Sie den linken Teilbaum untersuchen, auch wenn der rechte Teilbaum leer ist, und Sie müssen den rechten Teilbaum untersuchen, auch wenn der linke Teilbaum leer ist. Beobachten Sie also, wo Sie die rekursiven Aufrufe platzieren.
Um zu testen, ob der Baum ein Suchbaum ist, müssen Sie die Datenwerte überprüfen. Sie haben bereits etwas in der Nähe des richtigen Vergleichs. nicht ganz richtig. Schreiben Sie einige 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 Platz finden, an dem Sie das Ergebnis der Gültigkeitsprüfung ablegen können. Beobachten Sie erneut, wo Sie die rekursiven Aufrufe platzieren (wenn Sie nur diesen Teil ausführen, gibt es mehrere Lösungen, aber machen Sie sich in diesem Stadium keine Sorgen, wenn Sie nur eine sehen).
Wenn Sie es schließlich geschafft haben, beide Funktionen separat zu schreiben und sie an einigen Beispielen getestet haben, setzen Sie sie sorgfältig zusammen (falls dies für die Zuweisung erforderlich ist).
quelle
In solchen Dingen ist es oft einfacher, rückwärts zu denken. Überlegen Sie also zuerst, was Sie brauchen. Lassen Sie uns anhand Ihrer Beschreibung Folgendes auflisten:
OK, das ist eine ziemlich kurze Liste, diese sollte überschaubar sein. Beginnen wir mit einer leeren Methode und fügen eine Beschreibung hinzu, was passieren soll.
Jetzt Gültigkeit. Wie prüft man die Gültigkeit? Im Chat sagten Sie, ein Baum sei gültig, "wenn ... alle linken Kinder kleiner als die Eltern sind und die rechten Kinder größer als die Eltern". Ich bin sicher, Sie wollten auch Gleichheit zulassen. Das wäre
t.left.value <= t.value <= t.right.value
.Aber was ist, wenn eines der Kinder vermisst wird? Nach allem, was Sie gesagt haben, wissen Sie, dass der Knoten noch gültig ist, wenn einer fehlt (oder beide fehlen). Fügen wir dies hinzu und strukturieren uns leicht um:
OK, wir wissen jetzt, ob dieser Knoten gültig ist. Wie prüfen wir, ob der gesamte Baum gültig ist? Es befindet sich nicht in einem Array, daher können / wollen wir es wahrscheinlich nicht linear durchlaufen. Ihre Aufgabe gibt die Antwort: Rekursion. Aber wie akkumulieren wir eine Antwort durch Rekursion? Wir haben Zugriff auf drei Informationen, ob dieser Knoten gültig ist, und das Ergebnis von Aufrufen, in denen gefragt wird, ob der linke und der rechte Knoten gültig sind. Offensichtlich ist der Baum nur gültig, wenn alle drei wahr sind.
Wenn Sie aufpassen, sagt uns das sogar, was unsere Funktion zurückgeben muss.
Wie integrieren wir nun die Zählung? Sie sagen, was zählt ("ein übergeordneter Knoten mit linken und rechten untergeordneten Knoten"), und das sollte nicht schwer in tatsächlichen Code zu übersetzen sein. Überprüfen Sie, ob diese Bedingung erfüllt ist, und erhöhen Sie den Zähler entsprechend. Denken Sie daran, dass dies irgendwo sein muss, wo es jedes Mal erreicht wird, wenn es wahr ist.
Und natürlich habe ich einige Details wie die Rekursionsstoppbedingung weggelassen und nach Null gesucht.
quelle
Meine drei obigen Kommentare sind drei Hinweise auf Probleme mit Ihrem Code.
node1.value < node2.value
if
Wert zutrifft. Sind Sie sicher, dass Sie dies beabsichtigt haben? Übrigens möchten Sie vielleicht überprüfen, ob die if-Anweisung das tut, was Sie wollen.quelle