Bei einer gegebenen BST muss ich die Anzahl der linken Knoten des Baumes finden.
Beispiel:
%Vor%Die Antwort sollte 4 sein, da (5, 1, 4, 7) alle linken Knoten des Baumes sind.
Was ich tun möchte, ist:
%Vor%Ich weiß, dass es falsch ist, aber ich weiß nicht warum. Könnte jemand erklären, warum, und mir auch bei der Antwort helfen.
Es ist nicht notwendig, einen Akkumulator (den count -Parameter) in der Aufrufliste weiterzuleiten, da Sie nicht auf die Tail-Rekursion angewiesen sind.
Ich denke, du musst deinen Code ein wenig umstrukturieren. Übergeben Sie die aktuelle Anzahl für linke Knoten nicht, sondern empfangen Sie sie einfach von den zwei untergeordneten Knoten und addieren Sie sie.
Ich denke, die eleganteste Lösung ist diese. Ja, natürlich bin ich voreingenommen. Ich bin ein Mensch: -)
%Vor%Indem Sie den Indikator für die linken Knoten nach unten übergeben, vereinfacht sich das, was weitergegeben werden muss. Das folgende Diagramm zeigt, dass jede Summe übergeben wird - Sie beginnen unten und jede Null geht über 0 hinaus.
Jeder Knoten auf der linken Seite geht um 1 plus, was auch immer von beiden Zweigen kam. Jeder Knoten auf der rechten Seite übergibt 0 plus was auch immer von beiden Zweigen kam.
Die Wurzel fügt nichts hinzu, da sie weder ein linker noch ein rechter Knoten ist (sie wird genauso behandelt wie rechts).
%Vor%Sie können die Operation aus diesem vollständigen Programm sehen:
%Vor%gibt die Debugging-Zeilen aus:
%Vor% Die nicht-debuggende Version der Funktion countLeft ist so einfach wie der Pseudocode am Anfang dieser Antwort:
Tags und Links binary-tree