Dieser Artikel beschreibt die Java -Methode, um alle Wege des binären Baums zu drucken. Teilen Sie es für Ihre Referenz wie folgt weiter:
Frage:
Geben Sie einen binären Baum und drucken Sie alle Wege aus.
Zum Beispiel sind für den folgenden binären Baum alle seine Wege:
8 -> 3 -> 1
8 -> 2 -> 6 -> 4
8 -> 3 -> 6 -> 7
8 -> 10 -> 14 -> 13
Ideen:
Starten Sie vom Stammknoten aus, geben Sie Ihren eigenen Wert in ein Array und übergeben Sie dieses Array an seinen Kinderknoten. Der untergeordnete Knoten setzt auch seinen eigenen Wert in dieses Array ein und übergibt ihn an seinen Kinderknoten, bis dieser Knoten ein Blattknoten ist, und druckt dann das Array aus. Wir müssen hier also Rekursion verwenden.
Code:
/** Druckt ein binäres Baum, druckt alle Wurzel-Blatt-Blattwände pro Zeile aus. Verwendet einen rekursiven Helfer, um die Arbeit zu erledigen. PrintPaths (Root, Pfad, 0);}/** rekursive PrintPaths-Helfer-gegeben einen Knoten und ein Array, das den Pfad vom Root-Knoten bis hin zu diesem Knoten enthält, druckt alle Root-Blatt-Pfade aus. // diesen Knoten an den Pfadarray -Pfad anhängen [Pathlen ++] = node.value; // Es ist ein Blatt. Drucken Sie also den Pfad, der hier geführt hat, wenn (node.leftchild == null && node.rightchild == null) {printArray (Pfad, Pathlen); } else {// Ansonsten versuchen Sie beide Subtrees PrintPaths (Node.LeftChild, Path, Pathlen); printPaths (Knoten.RightChild, Pfad, Pathlen); }}/** Dienstprogramm, das Zeichenfolgen aus einem Array in einer Zeile druckt. } System.out.println ();}Hinweis: Sie können nur ein Array + einen Wert verwenden, um den erforderlichen Pfad zu drucken. Wenn Sie eine verknüpfte Listenstruktur wie LinkedList verwenden, funktioniert sie nicht. Es lohnt sich, die Gründe zu analysieren, es ist sehr interessant.
Für weitere Informationen zu Java -Algorithmen können Leser, die an dieser Website interessiert sind, die Themen "Java -Datenstruktur und Algorithmus -Tutorial", "Zusammenfassung der Java -Operation DOM -Knoten -Tipps", "Zusammenfassung der Java -Datei- und Verzeichnisoperationstipps" und "Zusammenfassung der Java -Cache -Operation Tipps" anzeigen
Ich hoffe, dieser Artikel wird für Java -Programme aller hilfreich sein.