Dies ist eine gemeinsame Interviewfrage, beispielsweise die hierarchische Durchquerung des binären Baums durch die Vorbestellung und die in Ordnung des Binärbaums usw.
Vorbestellung + mittlerer Reihenfolge -> Build
Angenommen, es gibt jetzt einen binären Baum wie folgt:
Zu diesem Zeitpunkt lautet die Traversalordnung:
Vorbestellung: GdafemHz in Ordnung: ADEFGHMZ POSTORDER: AEFDHZMG
Geben Sie nun Vorbestellung und In-Ordnung (in Ordnung), erstellen
Definition des Baumknotens:
Klassenbaum {char val; Baum links; Baum rechts; Baum (char val, baum links, baum rechts) {this.val = val; this.left = links; this.right = rechts;} Baum () {} Baum (char val) {this.val = val;Erfolge machen:
public static tree buildtree (char [] vorbestellt, char [] inOrder) {// Vorbestellung ist die Vorbestellungssequenz // InOrder ist die mittlere Sequenz, wenn (vorbestellt == null || vorbestellt.length == 0) {return null;} Baumwurzel = neuer Baum (vorbestellt [0]; // Ermitteln Sie die Position, die in der Position von in Ordnung in Ordnung in Ordnung ist. for (char i = 0; i < inOrder.length; i++){if(inOrder[i] == root.val){inOrderIndex = i;}}//The left subtree and right subtree part of preOrder char[] preOrderLeft = Arrays.copyOfRange(preOrder, 1, 1+inOrderIndex);char[] preOrderRight = Arrays.copyOfRange(preOrder, 1+in OrderIndex, Vorbestellung.Length); // Der linke Teilbaum und den rechten Teil der Subree -Teil von InOrder char [] inOrderLeft = arrays.copyofrange (in Order, in OrderIndex); char [] in OrderRight = Arrays.Copyofrange (befindlich, in OrderIndex 1 1, in der linken Subtree -Subtree -Subtree -Subtree -Subree -Subree -Subree -Subree -Subree -Struktur. Buildtree (vorOrderLeft, in OrderLeft); Tree RightChild = Buildtree (vorbestellig, in Ordnung); Root.Left = linkChild; root.right = rightchild; return root;}Es ist tatsächlich dasselbe, eine mittlere Bestellung + nach der Bestellung zu erstellen. Ich werde es hier nicht schreiben
Verschiedene Traverals
Nach der Bestellung von Traversal
public static void postorderPrint (Baumwurzel) {// nachfolgende Durchqueren // links und rechte Wurzeln if (root.left! = null) {postorderPrint (root.left); } if (root.right! = null) {postorderPrint (root.right); } System.out.print (root.val + ""); }Erfahren Sie aus einem Beispiel und die Reihenfolge ist die gleiche wie die Reihenfolge in der Mitte. Ich werde es hier nicht schreiben
Layer -Sequenz -Traversal
Sie können eine Warteschlangewarteschlange verwenden, um den Stammknoten zuerst zur Warteschlange hinzuzufügen. Wenn die Warteschlange nicht leer ist, nehmen Sie den Knotenknoten der Warteschlangenheader und drucken Sie den Knotenwert des Knotens aus. Wenn die linken und rechten Kinder des Knotens nicht leer sind, fügen Sie die linken und rechten Kinder in die Warteschlange hinzu.
public static void LayerOrderprint (Baumwurzel) {if (root == null) {return; } // Layer -Sequenz -Traversal -Warteschlange <baums> qe = new LinkedList <baum> (); qe.add (root); while (! qe.isempty ()) {baum node = qe.poll (); System.out.print (node.val + ""); if (node.left! = null) {qe.add (node.left); } if (node.right! = null) {qe.add (node.right); }}}Tiefe und Breite Priorität
Tatsächlich ist es nur ein anderes Sprichwort. Die Priorität der Tiefe ist vorbestellt, die BREAN-PROIMITÄT ist durchquert.
public static void DeepFirstprint (Baumwurzel) {// Tiefe Prioritätsquelle entspricht dem Vorbestellungs -Traversal //, sodass Sie direkt vorbestellt werden können, wenn (root == null) {return; } System.out.print (root.val + ""); if (root.left! = null) {DeepFirstprint (root.left); } if (root.right! = null) {DeepFirstprint (root.right); }} public static void DeepFirstprintnonerec (Baumwurzel) {// Die nicht recursive Form der Tiefenprioritäts-Traversal if (root == null) {return; } Stack <baum> st = neuer stapel <baum> (); St.Add (Wurzel); while (! St.Isempty ()) {Tree node = St.Pop (); System.out.print (node.val + ""); // Der Stapel ist wieder in und zuerst aus // fügen Sie zuerst das rechte Kind und dann das linke Kind zu, wenn (Knoten.Right! = NULL) {St.Add (Knoten.Right); } if (node.left! = null) {St.Add (node.left); }}}Hauptfunktion:
public static void main (String [] args) {char [] vorbestellt = "gdafemhz" .tocharArray (); char [] inOrder = "adefghmmz" .tocharArray (); Tree root = main.buildtree (vorbestellt, in Ordnung); // main.postorderPrint (root); // postorder traversal // main.layerOrderPrint (root); // Layer -Sequenz traversal // main.deepfirstprint (root); // Tiefe Priorität traversal // main.deepfirstprintnonerec (root); // die nicht rezisive Version von Tiefen-First-Traversal}Zusammenfassen
In der oben genannten Bearbeitung geht es um die Gründung von Binärbäumen und verschiedenen Traversal -Instanzcodes in Java. Ich hoffe, es wird für alle hilfreich sein. Interessierte Freunde können weiterhin auf diese Seite verweisen:
" Einführung in zwei Methoden zur Spiegelung in Java -Programmieren binärer Bäume "
" Java -Sprache beschreibt die Tiefe und Breite des binären Baumes "
Java -Binärbaumpfad und Codebeispiel
Wenn es Mängel gibt, hinterlassen Sie bitte eine Nachricht, um darauf hinzuweisen. Vielen Dank an Freunde für Ihre Unterstützung für diese Seite!