Eine, binäre Sortierbaumdefinition
1. Definition des binären Sortierbaums <br /> binärer Sortierbaum (binärer Sortierbaum), auch als binärer Suchbaum bezeichnet. Es ist definiert als: ein binärer Sortierbaum oder ein leerer Baum oder ein binärer Baum, der die folgenden Eigenschaften erfüllt:
① Wenn der linke Unterbaum nicht leer ist, sind die Werte aller Knoten auf dem linken Subtree kleiner als der Wert des Stammknotens;
② Wenn sein rechter Unterbaum nicht leer ist, sind die Werte aller Knoten auf dem rechten Teilbaum größer als die Werte des Stammknotens;
③Die linke und rechte Unterbäume selbst sind jeweils ein binärer Sortierbaum.
Die obigen Eigenschaften werden als Binärsortierbaum (BST -Eigenschaft) bezeichnet, sodass der binäre Sortierbaum tatsächlich ein binärer Baum ist, der die BST -Eigenschaft erfüllt.
2. Eigenschaften des Binärsortierbaums <br /> den binären Sortierbaum in mittlerer Ordnung übertragen, und die resultierende Durchlaufsequenz mit mittlerer Ordnung ist eine inkrementelle Reihenfolge.
3. Setzen Sie den binären Sortierbaum <br /> einen neuen Knoten in den binären Sortierbaum ein, um sicherzustellen, dass der eingefügte binäre Baum immer noch der Definition des binären Sortierbaums erfüllt.
Vorgang einfügen:
Wenn der binäre Sortierbaum leer ist, wird der Knoten *als Wurzelknoten in den leeren Baum eingefügt;
Wenn es nicht leer ist, vergleichen Sie die Schlüsselwort S-> Taste, die mit dem Schlüsselwort T-> Taste für Baumwurzel eingefügt werden soll. Wenn S-> Key = T-> Schlüssel, müssen Sie es nicht einfügen. Wenn S-> Schlüssel <T-> Schlüssel, wird es in den linken Unterbaum der Wurzel eingefügt. Wenn S-> Schlüssel> T-> Schlüssel, wird es in den rechten Unterbaum des Wurzels eingefügt. Der Insertionsprozess im Subtree entspricht dem Einfügenprozess im Baum. Dies setzt sich fort, bis der Knoten *S als neues Blatt in den binären Sortierbaum eingefügt wird oder bis der Baum Knoten mit denselben Schlüsselwörtern aufweist.
4. Suchen Sie nach Binärsortierbaum <br /> unter der Annahme, dass der Wurzelzeiger des binären Sortierbaums root ist und der angegebene Schlüsselwortwert k ist, der Suchalgorithmus kann beschrieben werden als:
① Setzen Sie den Anfangswert: q = root;
② Wenn k = q -> Schlüssel, ist die Suche erfolgreich und der Algorithmus endet;
③ Andernfalls wird der linke Teilbaum von Q an Q und dann der Schritt ② gesendet, wenn k <q －＞ Schlüssel und der linke Teilbaum von q nicht leer sind; Andernfalls schlägt die Suche fehl und der Algorithmus endet;
④ Ansonsten wird, wenn k ＞ q －＞ Schlüssel und der richtige Teilbaum von Q nicht leer sind, der rechte Teilbaum von q an Q und dann der Schritt ②; Andernfalls schlägt die Suche fehl und der Algorithmus endet.
5. Löschen des binären Sortierbaums <br /> Angenommen, der gelöschte Knoten ist *p und die Eltern sind *f, was in der Allgemeinheit nicht verloren geht. Angenommen, *P ist das linke Kind von *f, ist das Folgende in drei Situationen unterteilt:
⑴ Wenn Knoten *P ein Blattknoten ist, müssen Sie nur den Zeiger seines übergeordneten Knotens *f ändern.
⑵ Wenn der Knoten *p nur das linke Subbree PL oder nur den rechten Subtree -PR hat, dann machen Sie einfach PL oder PR zum linken Unterbaum seines übergeordneten Knotens.
⑶ Wenn die linken und rechten Teilbänder des Knotens *p nicht leer sind, finden Sie zuerst den Vorgänger mittleren Ordnung (oder Nachfolger) Knoten *S von *p (beachten Sie, dass *s der untere rechts Noten im linken Subtree von *p ist, und der rechte Kettendomäne ist leer), und dann gibt es zwei Möglichkeiten: ① Der linke Untertree. zur rechten Kette von *Ps mittlerem Ordnung Vorgängerknoten *s. ② Ersetzen Sie *p durch den Vorgängerknoten mit mittlerer Ordnung *s von *p (dh die Daten von *s in *p) und ketten Sie den linken Teilbaum von *s zur linken (oder rechten) Kette des übergeordneten Knotens *q von *s.
6. Durchqueren von Binärbäumen <br /> Es gibt drei Möglichkeiten, binäre Bäume wie folgt zu durchqueren:
(1) Vorbestellungsquellen (DLR), zuerst auf den Wurzelknoten zugreifen, dann den linken Subtree durchqueren und schließlich den rechten Subtree durchqueren. Abkürzte Wurzel - links - rechts.
. Abgekürzte Anmerkung: linksgerecht.
(3) Nach der Bestellung durch-Ordnung (LRD), zuerst den linken Unterbaum durchqueren, dann den rechten Subtree durchqueren und schließlich auf den Stammknoten zugreifen. Abgekürzte links-rechts-Root.
2. Code schreiben
1. Definition der Baumknotenklasse 0
Paket com.lin; / ** * Funktionsübersicht: */ öffentliche Klasse Treenode {öffentliche Integer -Daten; /* Elternknoten dieses Knotens*/ public Treenode Eltern; /*Linkskinderknoten dieses Knotens*/ Public Treenode links; /*Rechts Kinderknoten dieses Knotens*/ public Treenode rechts; public treenode (Integer data) {this.data = data; } @Override public String toString () {return "treenode [data =" + data + "]"; }} 2. Definition des binären Sortierbaums
Paket com.lin; /*** Funktionszusammenfassung: Sortieren/ausgeglichener binärer Baum*/öffentliche Klasse SearchTree {public treenode root; öffentliche lange Größe; / ** * Node zum Baum hinzuzufügen System.out.println ("Daten wurden erfolgreich in den ausgewogenen Binärbaum eingefügt"); zurückkehren; } Treenode treeenode = new treenode (Daten); // Die Daten, die Treenode currentNode = root eingefügt werden sollen; Treenode ParentNode; while (true) {parentNode = currentNode; // Speichern Sie den übergeordneten Knoten // Die eingefügten Daten sind kleiner als der übergeordnete Knoten if (currentNode.data> data) {currentNode = currentNode.left; // Der linke untergeordnete Knoten des aktuellen übergeordneten Knotens ist leer, wenn (null == currentNode) {parentNode.left = treenode; treenode.parent = parentNode; System.out.println ("Daten wurden erfolgreich in den binären Suchbaum eingefügt"); Größe ++; zurückkehren; } // Die eingefügten Daten sind größer als der übergeordnete Knoten} else if (currentNode.data <data) {currentNode = currentNode.Right; // Der rechte untergeordnete Knoten des aktuellen übergeordneten Knotens ist leer, wenn (null == currentNode) {parentNode.right = treenode; treenode.parent = parentNode; System.out.println ("Daten werden erfolgreich in den binären Suchbaum eingefügt"); Größe ++; zurückkehren; }} else {system.out.println ("Die Eingabedaten entsprechen den Daten des Knotens"); false zurückgeben; }}} / ** * @param data * @return treenode * / public treenode findTreenode (Integer data) {if (null == root) {return null; } Treenode current = root; while (current! = null) {if (current.data> data) {current = current.left; } else if (current.data <data) {current = current.right; } else {return current; }} return null; }} Hier finden Sie eine Methode zum Hinzufügen und Suchen
3. Vorder-, Mittel- und Rückfahrten
Paket com.lin; import Java.util.stack; / *** Funktionszusammenfassung:*/ public class Treeorder {/ *** rekursive Implementierung von Vorbestellungen Traversal* @Author Liningwen* @Since 29. August 2015* @param treenode*/ public static void vorbestelltMethodone (Treenode Treenode) {if (null! if (null! } if (null! }}} / *** Looping zum Implementieren von Vorbestellungen von Treversal* @param treenode* / public static void vorbestelltMethodtwo (treenode treeenode) {if (null! stack.push (treenode); while (! stack.isempty ()) {treenode tempnode = stack.pop (); System.out.print (tempnode.data + ""); // Der richtige untergeordnete Knoten ist nicht null, geben Sie den richtigen untergeordneten Knoten in if (null! = Tempnode.right) {stack.push (tempnode.right); } // Nach dem Einsetzen des rechten untergeordneten Knotens den linken untergeordneten Knoten und nimm if (null! = Tempnode.left) {stack.push (tempnode.left); }}}} / *** rekursiv in Ordnung in Ordnung implementieren } System.out.print (treenode.data + ""); if (null! }}} / *** Schleife Implementierung In-Ordnung-Traversal* @param treenode* / public static void medorderMethodtwo (treenode treeenode) {stack <treenode> stack = new stack <treenode> (); Treenode current = treenode; while (current! = null ||! stack.isempty ()) {while (current! current = current.left; } if (! stack.isempty ()) {current = stack.pop (); System.out.print (current.data+""); Strom = Strom.Right; }}} / *** rekursiv implementieren nach der Bestellung von Traversal* @param treenode* / public static void postorderMethodone (Treenode treenode) {if (null! = Treenode) {if (null! } if (null! } System.out.print (treenode.data + ""); }} / *** Looping zum Implementieren von Nachbestellungen durch den Bestellung* @param treenode* / public static void postordermethodtwo (treenode treenode) {if (null! Treenode current = treenode; Treenode rightnode = null; while (current! = null ||! stack.isempty ()) {while (current! current = current.left; } current = stack.pop (); while (current! rightnode = current; if (stack.isempty ()) {System.out.println (); zurückkehren; } current = stack.pop (); } stack.push (Strom); Strom = Strom.Right; }}}} 4.. Wie man benutzt
Paket com.lin; / ** * Funktionszusammenfassung: */ public class SearchTreetest {/ ** * @param args */ public static void main (String [] args) {SearchTree tree = new SearchTree (); tree.addtreenode (50); tree.addtreenode (80); tree.addtreenode (20); tree.addtreenode (60); tree.addtreenode (10); tree.addtreenode (30); tree.addtreenode (70); tree.addtreenode (90); tree.addtreenode (100); tree.addtreenode (40); System.out.println("===================================================================================================== ================================================================= ================================================================= ================================================================= ================================================================= ================================================================= ================================================================= System.out.println ("================================================= ====================================================================== ====================================================================== ======================================================================= ====================================================================== ====================================================================== ====================================================================== ======================================================================= TreeOrder.PostorderMethodone (Tree.root); System.out.println("====================================================================================================== ================================================================= =================================================================== ================================================================= =================================================================== ================================================================= =================================================================== System.out.println ("================================================= ====================================================================== ====================================================================== ======================================================================= ====================================================================== ====================================================================== ====================================================================== ======================================================================= TreeOrder.MedorderMethodtwo (Tree.root);Ausgangsergebnis:
Ebenso lautet der Suchprozess wie folgt:
Treenode node = tree.findTreenode (100); System.out.println (Knoten);
Das Ergebnis ist korrekt
Das obige ist eine detaillierte Einführung in den Java -binären Sortierbaum. Ich hoffe, es wird hilfreich für das Lernen aller Java -Programme.