Dieser Artikel beschreibt die Tiefe-First-Traversal- und Breite-First-Traversal-Algorithmen, die Binärbaum in Java implementieren. Teilen Sie es für Ihre Referenz wie folgt weiter:
1. Analyse
Die übliche Praxis der Nichtrevolle der Tiefe zuerst durch Binärbäume besteht darin, einen Stapel zu übernehmen, und die übliche Praxis der Nichtrecursivität der Breite-First-Traversal besteht darin, eine Warteschlange zu übernehmen.
Tiefe-First-Traversal : Jeder mögliche Ast-Pfad kann durchdrungen werden, bis er nicht weiter tief sein kann und jeder Knoten nur einmal zugegriffen werden kann. Es ist zu beachten, dass die Tiefe-First-Traversal des binären Baums etwas Besonderes ist und in Vorbestellungen, Zwischenquellen und anschließender Durchqueren unterteilt werden kann. Die spezifische Beschreibung lautet wie folgt:
Erster Ordnung Traversal : Für jeden Subtree zuerst Zugang zur Wurzel, dann den linken Subtree durchqueren und schließlich seinen rechten Subtree durchqueren.
Middle Order Traversal : Für jeden Unterbaum zuerst durchqueren Sie den linken Subtree, dann auf die Wurzel zuzugreifen und schließlich den rechten Teilbaum zu durchqueren.
Nach der Bestellung Traversal : Für jeden Subtree durchqueren Sie zuerst den linken Subtree, durchqueren Sie dann seinen rechten Subtree und greifen Sie schließlich auf die Wurzel zu.
BROADTH-First-Traversal : Auch als Hierarchie bezeichnet und auf jede Ebene von oben nach unten zugreifen. Greifen Sie in jeder Ebene von links nach rechts (oder von rechts nach links) Knoten zu. Nach dem Zugriff auf eine Ebene geben Sie die nächste Ebene ein, bis keine Knoten vorhanden sind, auf die zugegriffen werden kann.
2. Geben Sie Beispiele an
Der in der folgende Abbildung gezeigte binäre Sortierbaum erfordert die Verwendung von Vorbestellungen (rekursiv, nicht rekursiv), in Ordnung, in Ordnung (rekursiv, nicht rekursiv), postordender Traversal (rekursiv, nicht recursive) und brodth-erste.
① Referenzcode
Paket BinaryTreetraversetest; import Java.util.linkedList; Import Java.util.queue;/** * Tiefe Priorität Traversal und Breite Priorität von Binärbäumen * @Author Fantasy * @version 1.0 2016/10/05 - 2016/107 */Public Class BinaryTeTeTeTest {public class) arm. BinarySorttree <Ganzzahl> tree = new BinarySorttree <Ganzzahl> (); Tree.insertNode (35); Tree.insertNode (20); Baum.insertNode (15); Tree.insertNode (16); Tree.insertNode (29); Tree.insertNode (28); Tree.insertNode (30); Tree.insertNode (40); Tree.insertNode (50); Tree.insertNode (45); Tree.insertNode (55); System.out.print ("Vorbestellung von Traversal (rekursiv):"); Tree.PreorderTraverse (Tree.getRoot ()); System.out.println (); System.out.print ("In-Ordnung-Traversal (rekursiv):"); Tree.inorderTraverse (Tree.getroot ()); System.out.println (); System.out.println (); System.out.print ("postbestellter Traversal (rekursiv):"); tree.postorderTraverse (Tree.getRoot ()); System.out.println (); System.out.print ("voraustrierender Traversal (nicht rekursiv):"); Tree.PreorderTraversenoreCursion (Tree.getroot ()); System.out.println (); System.out.print ("In-Ordnung-Traversal (nicht rekursiv):"); Tree.inorderTraversenoreCursion (Tree.getroot ()); System.out.println (); System.out.println (); System.out.print ("postbestellter Traversal (nicht rekursiv):"); Tree.PostorderTraversenoreCursion (Tree.getroot ()); System.out.println (); System.out.print ("BreadthPriority Traversal:"); Tree.BreadHfirsttraverse (Tree.getRoot ()); }}/*** Knoten*/Klasse Knoten <e erweitert vergleichbar <e >> {e Wert; Knoten <e> links; Knoten <e> recht; Node (e value) {this.Value = value; links = null; rechts = null; }}/** * Verwenden Sie eine Präzedenzfallsequenz, um einen binären Sortierbaum (auch als binärer Suchbaum bekannt) zu erstellen. BinarySorttree () {root = null; } public void InsertNode (Ewert) {if (root == null) {root = neuer Knoten <e> (Wert); zurückkehren; } Knoten <E> currentNode = root; wob brechen; } currentNode = currentNode.right; } else {if (currentNode.left == null) {currentNode.left = neuer Knoten <e> (Wert); brechen; } currentNode = currentNode.left; }}} public node <e> getRoot () {return root; } / ** * Vorbestellung durch den Binärbaum (rekursiv) * @param node * / public void vorOrdertraverse (Knoten <e> node) {System.out.print (node.value + ""); if (node.left! = null) vorOrderTraverse (node.left); if (node.right! = null) vorOrderTraverse (Knoten.Right); } / ** * In-Ordnung-Durchlauf des binären Baums (rekursiv) * @param node * / public void inOrderTraverse (Knoten <e> node) {if (node.left! = Null) inOrderTraverse (node.left); System.out.print (node.value + ""); if (node.right! } / ** * Nachbestellung durch Binärbaum (rekursiv) * @param node * / public void postOrderTraverse (Knoten <e> node) {if (node.left! = Null) postorderTraverse (node.left); if (node.right! = null) postorderTraverse (Knoten.Right); System.out.print (node.value + ""); } / ** * Vorbestellung durch den Binärbaum (nicht recursive) * @param root * / public void vorOrderTraversenoreCursion (Knoten <e> root) {LinkedList <Node <e >> stack = new LinkedList <Node <e >> (); Knoten <E> currentNode = null; stack.push (root); while (! stack.isempty ()) {currentNode = stack.pop (); System.out.print (currentNode.Value + ""); if (currentNode.right! = null) stack.push (currentNode.right); if (currentNode.left! = null) stack.push (currentNode.left); }} / ** * In-Ordnung-Durchlauf von Binärbaum (nicht rekursiv) * @param root * / public void InreiderTraversenoreCursion (Knoten <e> root) {LinkedList <Node <e >> stack = new LinkedList <node <e >> (); Knoten <E> currentNode = root; while (currentNode! = null ||! stapel CurrentNode = currentNode.left; } currentNode = stack.pop (); System.out.print (currentNode.Value + ""); currentNode = currentNode.right; }} / ** * Nachbestellung des Binärbaums (nicht recursive) * @param root * / public void postOrderTraversenoreCursion (Knoten <e> root) {LinkedList <Node <node <e >> stack = new LinkedList <Node <e >> (); Knoten <E> currentNode = root; Node <e> rightnode = null; while (currentNode! = null ||! stapel CurrentNode = currentNode.left; } currentNode = stack.pop (); // Der aktuelle Knoten hat keinen rechten Knoten oder den vorherigen Knoten (der Knoten, der ausgegeben wurde) der richtige Knoten des aktuellen Knotens, dann wird der aktuelle Knoten ausgegeben, während (currentNode.right == null || currentNode.right == Rightnode) {System.out.print (CurrentNode.Value + "); rightnode = currentNode; if (stack.isempty ()) {return; // Root -Ausgänge, die Traversal endet} currentNode = stack.pop (); } stack.push (currentNode); // Es gibt immer noch den richtigen Knoten, der keine Stromnode = currentNode.Right durchquert; }} / *** Breadth-First-Traverse-Binärbaum, auch als hierarchischer Binärbaum bezeichnet. Knoten <E> currentNode = null; queue.offer (root); while (! queue.isempty ()) {currentNode = queue.poll (); System.out.print (currentNode.Value + ""); if (currentNode.left! = null) queue.offer (currentNode.left); if (currentNode.right! = null) queue.offer (currentNode.right); }}}② Ausgangsergebnis
Vorbestellungen Traversal (rekursiv): 35 20 15 16 29 28 30 40 50 45 55
In-Ordnung-Traversal (Rekursion): 15 16 20 28 29 30 35 40 45 50 55
Postorder -Traversal (Rekursion): 16 15 28 30 29 20 45 55 50 40 35
Vorbestellung durchquer
In-Ordnung-Traversal (nicht rekursiv): 15 16 20 28 29 30 35 40 45 50 55
Postorder-Traversal (nicht rekursiv): 16 15 28 30 29 20 45 55 50 40 35
Breite Priorität Traversal: 35 20 40 15 29 50 16 28 30 45 55
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.