1. Konzept
Der binäre Suchbaum wird auch zu einem binären Sortierbaum. Es hat das Merkmal, dass ein Knoten zwei untergeordnete Knoten befriedigt werden muss. Der Wert des linken untergeordneten Knotens muss kleiner als der Wert des Knotens sein, und der Wert des rechten untergeordneten Knotens muss größer sein als der Wert des Knotens. Für Vergleiche von nicht-grundlegenden Typen kann die Komparatorschnittstelle implementiert werden. In diesem Artikel werden Int -Typ -Daten für den Betrieb verwendet.
Um einen binären Baum umzusetzen, müssen Sie mit seiner Erhöhung beginnen. Nur durch den Bau des Baumes können Sie andere Vorgänge nutzen.
2. Konstruktion von binärer Suchbaum
Wenn wir über die Zunahme von Binärbäumen sprechen, müssen wir zunächst eine Klasse erstellen, die einen Knoten darstellt. Die Klasse des Knotens hat mehrere Attribute, den Wert des Knotens, des übergeordneten Knotens, des linken Knotens und des rechten Knotens des Knotens. Der Code ist wie folgt
statischer Klassenknoten {Knoten übergeordnet; Knoten linker; Knoten RightChild; int val; public node (knoten übergeordnet, knoten linker, node rightchild, int val) {super (); this.Parent = Eltern; this.leftchild = linksCild; this.rightChild = RightChild; this.val = val; } public node (int val) {this (null, null, null, val); } öffentlicher Knoten (Knotenknoten, int val) {this (Knoten, Null, Null, Val); }}Hier verwenden wir die interne Klassenschreibmethode. Nach dem Erstellen des Knotenwerts bauen wir den gesamten Baum. Ein Baum muss zuerst einen Wurzelknoten haben und sich dann auf die verbleibenden untergeordneten Knoten erstrecken. In diesem Baum gibt es auch einige Attribute wie die Grundwurzel der Grundwurzelknoten und die Elementgröße im Baum. Wenn diese beiden Attribute verwendet werden, kann das Komparatorattribut hinzugefügt oder eine Standardimplementierung angegeben werden. Der spezifische Code ist wie folgt
öffentliche Klasse SearchBinaryTree {private Knotenwurzel; private intgröße; public SearchBinaryTree () {Super (); }}3.
Beim Hinzufügen von Elementen müssen Sie die Initialisierung des Stammknotens berücksichtigen. Im Allgemeinen gibt es zwei Typen: Wenn der Konstruktor dieser Klasse initialisiert wird, wird die Stammknotenwurzel initialisiert. Die zweite besteht darin, den Stammknoten hinzuzufügen, wenn das erste Element hinzugefügt wird. Beide funktionieren theoretisch, verwenden aber normalerweise die zweite faule Ladeform.
Beim Hinzufügen von Elementen müssen mehrere Situationen berücksichtigt werden
1. Beim Hinzufügen bestimmen Sie, ob das Root initialisiert wird. Wenn es nicht initialisiert wird, wird es initialisiert. Weisen Sie dem Stammknoten den Wert zu und fügen Sie eine Größe hinzu.
2. Da der Binärbaum -Suchbaum erfüllt, dass der Stammknotenwert größer als der linke Knoten ist und kleiner als der rechte Knoten ist, muss der eingefügte Wert zuerst mit dem Stammknoten verglichen werden. Wenn es groß ist, suchen Sie im richtigen Subtree. Wenn es klein ist, suchen Sie im linken Subtree. Bis ein Kinderknoten.
Die Insertion -Implementierung hier kann zwei Typen annehmen: eine Rekursion, zwei iterativ (d. H. Durch den Schleifenmodus).
3.1. Rekursive Versionsinsertion
public boolean add (int val) {if (root == null) {root = neuer Knoten (val); Größe ++; zurückkehren; } Node node = getAdApternode (root, val); Node newnode = neuer node (val); if (node.val> val) {node.leftchild = newnode; newnode.parent = node; } else if (node.val <val) {node.rightchild = newnode; newnode.parent = node; } else {// keine Verarbeitung vorerst} Größe ++; 19 return true; } /*** Holen Sie sich den übergeordneten Knoten des zu eingefügten Knotens. Der übergeordnete Knoten erfüllt einen der folgenden Zustände. * 5. Der Elternknoten ist leer* Wenn einer der oben genannten 5 Fälle erfüllt ist, wird er rekursiv aufhören. * @param node * @param val * @return */ private node getAdApternode (Knotenknoten, int val) {if (node == null) {return node; } // In den linken Subtree einfügen, aber es gibt keinen linken Unterbaum, if (node.val> val && node.leftchild == null) {return node; } // In den rechten Subtree einfügen, aber es gibt keinen rechten Unterbaum, auch zurück, wenn (node.val <val && node.rightchild == null) {return node; } // In den rechten Subtree einfügen, aber es gibt keinen rechten Unterbaum, auch zurück, wenn (node.val <val && node.rightchild == null) {return node; } // In den rechten Subtree einfügen, aber es gibt keinen rechten Unterbaum, auch zurück, wenn (node.val <val && node.rightchild == null) {return node; } // In den rechten Subtree einfügen, aber es gibt keinen rechten Unterbaum, auch zurückgeben if (node.leftchild == null && node.rightchild == null) {return node; } if (node.val> val && node.leftchild! = null) {return getAdaptarnode (node.leftchild, val); } else if (node.val <val && node.rightchild! } else {return node; }}Verwenden Sie Rekursion, finden Sie zuerst den Endpunkt der Rekursion und verwandeln Sie dann das gesamte Problem in ein Unterproblem. Im obigen Code ist die Logik ungefähr so: Stellen Sie zunächst fest, ob der Stammknoten initialisiert wird, und wenn sie nicht initialisiert wird, wird er initialisiert, und nach Abschluss kehrt er zurück und verwendet dann eine Funktion, um den angepassten Knoten zu erhalten. Fügen Sie dann den Wert ein.
3.2. Iterative Version
public boolean put (int val) {return putval (root, val); } private boolean putval (Knotenknoten, int val) {if (node == null) {// initialisieren Sie den Stammknoten node = new node (val); root = node; Größe ++; zurückkehren; } Node temp = node; Knoten p; int t; / ** * den besten Knoten durch DO während der Schleifenerteration erhalten, */ do {p = temp; t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.rightChild; } else {temp.val = val; false zurückgeben; }} while (temp! = null); Node newnode = neuer node (p, val); if (t> 0) {P.Leftchild = newnode; } else if (t <0) {p.rightchild = newnode; } Größe ++; zurückkehren; }Das Prinzip ist tatsächlich das gleiche wie die Rekursion, die den besten Knoten erhalten und auf diesem Knoten arbeiten soll.
In Bezug auf die Leistung ist es definitiv die beste iterative Version. Im Allgemeinen ist es im Allgemeinen die iterative Version, um die Daten zu betreiben.
4. Löschen
Es kann gesagt werden, dass beim Betrieb des binären Suchbaums die Löschung am kompliziertesten ist und es relativ viele Situationen zu berücksichtigen gibt. Wenn Sie einen Knoten im binären Suchbaum löschen, werden Sie sich auf jeden Fall die folgenden vier Situationen vorstellen.
1. Der zu gelöschte Knoten hat keine linken und rechten untergeordneten Knoten, wie in den Knoten D, E und G in der obigen Abbildung gezeigt
2. Der zu gelöschte Knoten ist nur der linke untergeordnete Knoten, wie z. B. Knoten B
3. Der zu gelöschte Knoten ist nur der richtige untergeordnete Knoten wie der F -Knoten
4. Der zu gelöschte Knoten hat sowohl linke Kinderknoten als auch rechte Kinderknoten wie A- und C -Knoten
In den ersten drei Situationen kann gesagt werden, dass es relativ einfach ist, während der vierte kompliziert ist. Lassen Sie uns den ersten analysieren
Wenn dies der Fall ist, kann beispielsweise der Knoten D gelöscht, der linke untergeordnete Knoten des Knotens B auf null gesetzt werden, und wenn der Knoten G gelöscht wird, kann der rechte untergeordnete Knoten des Knotens F auf null eingestellt werden. Welche Seite sollte eingestellt werden und sehen, welche Seite der gelöschte Knoten befindet.
In der zweiten Möglichkeit zum Löschen von Knoten B müssen Sie nur den linken Knoten des Knotens A auf Knoten D und den übergeordneten Knoten von Knoten D an A einstellen. Welche Seite eingestellt ist, hängt davon ab, welche Seite des gelöschten Knotens auf dem übergeordneten Knoten befindet.
Der dritte Typ entspricht dem zweiten Typ.
Der vierte Typ, der wie bereits erwähnt ein bisschen kompliziert ist, besteht beispielsweise darin, den C -Knoten zu löschen, den übergeordneten Knoten des F -Knotens auf Knoten A einzustellen, den linken Knoten des F -Knotens auf Knoten e zu setzen, den rechten Knoten von A auf Knoten F festlegen, den Elternknoten von E auf den Knoten f (dh er ersetzen den node ersetzen) und es gibt einen anderen Typ. Welches sollte also verwendet werden? Wenn der Löschknoten der Root -Knoten ist, wie soll ich ihn löschen?
Für den vierten Fall können Sie sich so vorstellen: Finden Sie den Nachfolgeknoten von C oder einen Knoten, löschen Sie den Nachfolgeknoten und setzen Sie den Wert des Nachfolgeknotens auf den Wert von C oder einem Knoten. Lassen Sie uns zunächst das Konzept der Nachfolgeknoten ergänzen.
Der Nachfolgerknoten eines Knotens im gesamten Baum muss zufrieden sein. Der Knoten mit dem kleinsten Wert im Set von Knoten, der den Knoten wert ist, ist der Nachfolgerknoten. Natürlich gibt es möglicherweise keine Nachfolgeknoten.
Für den vierten Fall muss der Nachfolgerknoten jedoch existieren und sich in seinem rechten Unterbaum befinden, und er erfüllt auch einen der Fälle, in denen es nur einen Kinderknoten oder keinen untergeordneten Knoten gibt. Der spezifische Grund kann davon gedacht werden, da der Nachfolgerknoten größer als der C-Knoten ist und der linke und rechte Unterabschnitt des C-Knotens im linken Unterabschnitt im rechten Unterbaum existieren muss. Zum Beispiel ist der Nachfolgeknoten von C f und der Nachfolgerknoten von A ist E. E.
Bei der obigen Analyse ist die Implementierung relativ einfach, der Code ist wie folgt
public boolean delete (int val) {node node = getNode (val); if (node == null) {return false; } Node parent = node.parent; Node lutchild = node.leftchild; Node rightchild = node.rightChild; // Alle folgenden übergeordneten Knoten sind leer. Dies bedeutet, dass der gelöschte Knoten der Root -Knoten ist, wenn (linkSchild == null && rightchild == null) {// keine untergeordneten Knoten if (parent! = Null) {if (parent.leftchild == node) {parent.leftchild = null; } else if (parent.rightchild == node) {parent.rightchild = null; }} else {// Der übergeordnete Knoten existiert nicht, was bedeutet, dass der gelöschte Knoten der Stammknoten root = null ist; } node = null; zurückkehren; } else if (linkschild == null && rightchild! = null) {// nur der rechte Knoten if (parent! } else if (Eltern! } else {root = rightChild; } node = null; zurückkehren; } else if (linkSchild! } else if (Eltern! } else {root = linkChild; } Return true; } else if (linkSchild! = null && rightchild! boolean delete = delete (temp); if (delete) {node.val = temp; } Nachfolger = null; zurückkehren; } return false; } /*** Finden Sie den Nachfolgerknoten des Knotenknotens* 1. Bestimmen Sie zuerst, ob der Knoten einen rechten Teilbaum hat. Wenn ja, suchen Sie nach dem Nachfolgerknoten aus dem linken Unterbaum des rechten Knotens. Wenn nicht, fahren Sie mit dem nächsten Schritt fort* 2. Ermitteln Sie den übergeordneten Knoten des Knotens. Wenn der richtige Knoten des übergeordneten Knotens gleich dem Knoten ist, suchen Sie weiter nach dem übergeordneten Knoten *, bis der übergeordnete Knoten null ist oder den richtigen Knoten finden, der nicht gleich dem Knoten entspricht. * Grund, der Nachfolgeknoten muss größer sein als der Knoten. Wenn es einen richtigen Teilbaum gibt, muss der Nachfolgerknoten im richtigen Subtree existieren. Dies ist der Grund für den ersten Schritt* Wenn es keinen richtigen Unterbaum gibt, kann es auch einen Großvaterknoten des Knotens geben (d. H. Der übergeordnete Knoten des Knotens oder den übergeordneten Knoten über dem übergeordneten Knoten). * Iterativ suchen Sie danach, wenn es vorhanden ist, gibt es den Knoten zurück, und wenn es nein gibt, gibt es null zurück while (rightchild.leftchild! = null) {rightchild = rightChild.leftchild; } RECHT RightChild zurück; } Node parent = node.parent; while (parent! = null && (node == parent.rightChild)) {node = parent; Parent = Elternteil.Parent; } Eltern zurückgeben; }Für eine bestimmte Logik finden Sie in der obigen Analyse. Ich werde den Text hier nicht beschreiben.
Zusätzlich zu dieser Implementierung ist eine weitere Implementierung in der Einführung in den Algorithmus bereitgestellt.
public boolean remove (int val) {node node = getNode (val); if (node == null) {return false; } if (node.leftchild == null) {// 1. Der linke Knoten existiert nicht, der rechte Knoten kann existieren, einschließlich zwei Situationen. Beide Knoten existieren nicht und nur der rechte Knoten existiert transplantiert (Knoten, Knoten.RightChild); } else if (node.rightchild == null) {// 2. Das linke Kind existiert, und der rechte Knoten existiert keine Transplantation (Knoten, Knoten.Leftchild); } else {// 3. Beide Knoten haben einen Knoten nachfolger = getuccessor (Knoten); // Holen Sie sich den Knoten -Nachfolgerknoten if (Nachfolger.Parent! Transplantation (Nachfolger, Nachfolger. Transplantation (Knoten, Nachfolger); Nachfolger.leftchild = node.leftchild; Nachfolger.Leftchild.Parent = Nachfolger; } Return true; } /*** Ersetzen Sie den untergeordneten Knoten durch Knotenknoten* @param root root node* @param node node zu löschen Schritt* 2. Bestimmen Sie, dass der Knotenknoten das Kind des übergeordneten Knotens ist (dh feststellen, ob der Knoten ein rechter Knoten oder ein linker Knoten ist). Nachdem Sie das Ergebnis erhalten haben, ersetzen Sie den untergeordneten Knoten durch einen Knotenknoten, dh, wenn der Knotenknoten ein linker Knoten ist, ist das Kind auch der linke Knoten. Knoten*/ if (node.parent == null) {this.root = child; } else if (node.parent.leftchild == node) {node.parent.leftchild = child; } else if (node.parent.rightchild == node) {node.parent.rightchild = child; } if (child! = null) {child.parent = node.parent; }}5. Suche
Die Suche ist ebenfalls relativ einfach, wurde aber tatsächlich implementiert, wenn es hinzugefügt wird. In tatsächlichen Situationen kann dieser Teil aus einer separaten Methode extrahiert werden. Der Code ist wie folgt
public node getNode (int val) {node temp = root; int t; do {t = temp.val-val; if (t> 0) {temp = temp.leftchild; } else if (t <0) {temp = temp.rightChild; } else {return temp; }} while (temp! = null); null zurückkehren; }6. Binärer Suchbaum durchquert
Nach dem Verständnis der Eigenschaften des binären Suchbaums ist klar, dass die Durchlauf der Zwischenordnung nacheinander von klein bis groß angeordnet ist. Hier ist der hier bereitgestellte Zwischenauftragscode, das hier bereitgestellt wird
public void print () {print (root); } private void print (Knoten root) {if (root! = null) {print (root.leftchild); System.out.println (root.val); // Wenn sich die Position in der Mitte befindet, ist die Reihenfolge in der Mitte. Wenn es sich vorne befindet, befindet es sich im Präzedenzfall, sonst handelt es sich um einen nachfolgenden Druck (Wurzel.RightChild); }} Zusammenfassen
Das obige ist die Java -Implementierung der vom Editor eingeführten Binär -Suchbaumfunktion. Ich hoffe, es wird für alle hilfreich sein. Wenn Sie Fragen haben, hinterlassen Sie mir bitte eine Nachricht. Der Herausgeber wird alle rechtzeitig antworten!