Was ist ein binärer Baum? Ich werde es hier nicht vorstellen. Sie können Baidu: einen binären Baum verwenden. Verwenden Sie hier Java, um den "Ausdruck binärer Baum" zu implementieren.
Definition des Ausdrucks Binärbaum
Der erste Schritt ist zu verstehen, was der Ausdruck binärer Baum ist. Zum Beispiel der Ausdruck: (a+b × (cd))-e/f. Das Einlegen von Zahlen in den Blattknoten und den Operator in den Zweigknoten bildet einen binären Baum. Da es einen Ausdruck speichert, wird es als "Ausdruck binärer Baum" bezeichnet.
Kinderstiefel sind vielleicht neugierig, wie dies gebaut wurde? Nehmen Sie 45+23*56/2-5 als Beispiel. Nehmen Sie zuerst die erste Nummer 45 heraus und legen Sie sie in den Blattknoten. Legen Sie nach "+" auf den Zweigknoten.
Dann setzen Sie "23", "*", "56", "/" und "2" nacheinander.
Endlich "-" und "5",
Das ist ungefähr das. (Ich habe diese Bilder selbst gezeichnet, es ist hässlich, schau sie dir einfach an (⊙⊙))
Schritte, um den Ausdruck binärer Baum aufzubauen
1. Erstellen Sie ein Knotenobjekt;
2. Unterscheiden Sie Operatoren und Daten und speichern Sie sie in der entsprechenden Liste (Warteschlange);
3. Nehmen Sie die ersten beiden Zahlen und einen Bediener heraus, um einen neuen Zahlenknoten zu bilden.
4. Wiederholen Sie Schritt 3, bis der Bediener fertig ist.
5. Lassen Sie den Wurzelknoten dem letzten Knoten gleich.
Implementierung des Ausdrucks Binärbaum
Erstellen Sie zunächst die Knoten -Objektklasse, einschließlich Daten, linker Subtree, rechter Subtree und mehreren Set- und Methoden.
Paket tets0714;/** * Knotenobjektklasse * @author yuxiu * */public class Node {// Daten private Zeichenfolge Daten; // links SUBREE Private Knode Lchild; // Right Subtree Private Node Rchild; Node () {} node (String -Daten) {this.data = data; } Node (String -Daten, Knoten lchild, Knoten rchild) {Super (); this.data = Daten; this.lchild = lchild; this.rchild = rchild; } public String getData () {returndaten; } public node getLchild () {return lchild; } public node getrchild () {return rchild; }}Bauen Sie dann den Ausdruck Binärbaum.
Paket tets0714; import Java.util.ArrayList;/** * Ausdruck binärer Baumklasse * @author yuxiu * */public class formalUeTree {private String s = ""; private Knotenwurzel; // Root -Knoten/*** Ausdruck Binärer Baum erstellen* @param str expression*/public void creeTree (String str) {// eine Array -Liste deklarieren, Operatoren hinzufügen, subtrahieren, multiplikation und Division, ArrayList <string> operatorlist = new ArrayList <string> (); // eine Array -Liste deklarieren, Knotendaten speichern, ArrayList <node> tumlist = new ArrayList <node> (); // Unterscheiden Sie zunächst den Bediener und speichern Sie ihn in der entsprechenden Liste für (int i = 0; i <str.length (); i ++) {char ch = str.charat (i); // Die Zeichen der Zeichenfolge abrufen if (ch> = '0' && ch <= '9') {s+= ch; } else {tumlist.add (neuer Knoten (s)); s = ""; OperatorList.add (ch+""); }} // Fügen Sie die letzte Nummer in die Numberknoten -Numlist.add (neue Knoten)); while (operList.size ()> 0) {// Schritt 3, wiederholen Sie den zweiten Schritt, bis der Bediener fertig ist. Node right = numlist.remove (0); String operator = operatorList.remove (0); Node node = neuer node (oper, links, rechts); Numlist.Add (0, Knoten); // Bevorzugen Sie den neuen Knoten als erster Knoten, und der vorherige Knoten mit Index = 0 wird in Index = 1} // Schritt 4 geändert. Lassen Sie den Stammknoten gleich dem letzten Knoten root = tumlist.get (0); } / *** Knotendaten ausgabe* / public void output () {output (root); // STOP TRAVERSAL vom Stammknoten}/*** Ausgabeknotendaten* @param -Knoten*/public void output (Knotenknoten) {if (node.getLchild ()! } System.out.print (node.getData ()); // Transaktion umfasst Vorbestellungen-Traversal (links und rechts Root), in Ordnung durchlaufenal (linke Wurzel rechts) und postorder-Traversal (linke Wurzel rechts) if (node.getRchild ()! = Null) {output (node.getRchild ()); }} public static void main (String [] args) {formalUeTree tree = new FormalUeTree (); Tree.CreatTree ("45+23*56/2-5"); // Erstellen Sie den binären Baum des Expression Tree.output (); // Ausgabeüberprüfung}} Schließlich können Sie "45+23*56/2-5" in der Konsole ausgeben, ok. In der hier verwendeten mittleren Reihenfolge können Freunde versuchen, wie sich die Durchlauf von Vorbestellungen und POSTORDERS -Traversal auswirkt. Was Traversal betrifft, werden wir später darüber sprechen.
Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, es wird für das Lernen aller hilfreich sein und ich hoffe, jeder wird Wulin.com mehr unterstützen.