Java implementiert binäre Suchbaum und implementiert die Suche, Einfügen und Löschen von Operationen auf dem Baum (zusammengeführt und löschen, kopieren und löschen).
Zunächst müssen wir ungefähr wie folgt eine Codierungsidee haben:
1. Suche: Gemäß den Dateneigenschaften des binären Suchbaums können wir die Suche basierend auf dem Wertvergleich von Knoten realisieren. Wenn der Suchwert größer ist als der aktuelle Knoten, gehen Sie nach rechts und umgekehrt!
2. Einfügen: Wir sollten wissen, dass alle eingefügten Blattknoten sind. Daher müssen wir die Position des zu eingefügten Blattknotens ermitteln, und die Einfügungsidee stimmt mit der Suchidee überein.
3.. Löschen:
1) Zusammenführen und löschen: Im Allgemeinen werden die folgenden Situationen auftreten. Der gelöschte Knoten hat einen linken Subtree, aber keinen rechten Unterbaum. Zu diesem Zeitpunkt sollte der übergeordnete Knoten des aktuellen Knotens auf den linken Unterbaum des aktuellen Knotens verweisen. Wenn der gelöschte Knoten einen rechten Teilbaum, aber keinen linken Unterbaum hat, sollte der übergeordnete Knoten des aktuellen Knotens auf den rechten Teilbaum verweisen. Wenn der gelöschte Knoten einen linken Subtree und einen rechten Unterbaum hat, können wir den rechtlichen Knoten des linken Unterbaums des gelöschten Knotens finden und dann den rechten oder linken "Zeiger" dieses Knotens auf den rechten Subtree des gelöschten Knotens zeigen
2) Kopieren und Löschen: Kopieren und Löschen sind relativ einfache Löschvorgänge und sind auch die am häufigsten verwendeten Löschvorgänge. Es gibt ungefähr drei Situationen: Wenn der aktuelle Knoten keinen linken Unterbaum hat und einen rechten Unterbaum hat, lassen Sie den Stammknoten des aktuellen rechten Teilbaums den gelöschten Knoten ersetzen. Wenn der aktuelle Knoten keinen rechten Subtree hat und einen linken Unterbaum aufweist, lassen Sie den Stammknoten des aktuellen linken Teilbaums und ersetzen Sie den gelöschten Knoten. Wenn der aktuell gelöschte Knoten sowohl einen linken Subtree als auch einen rechten Unterbaum hat, müssen wir den Subtree des gelöschten Knotens finden und den linken Subtree den Wert des linken Nodens finden und den Wert dieses Knotens dem gelöschten Knoten zulassen. Es). Sie können diesen Prozess auch als eigenständiger Knoten am linken Knoten des rechten Teilbaums des aktuell gelöschten Knotens implementieren.
Fügen wir als nächstes den Code hinzu.
Zunächst einmal ## Binary Search Tree Node Class ## ##
Package SearchBinaryTree; Public Class SearchBinaryTreenode <T> {t Data; öffentliche SucheBaryTreenode <T> linkSchild; öffentliche SucheBinaryTreenode <t> rightChild; public SearchBinaryTreenode () {this.data = null; this.leftchild = this.rightchild = null; } public SearchBaryTreenode (t da) {this.data = da; this.leftchild = this.rightchild = null; } public SearchBaryTreenode (t da) {this.data = da; this.leftchild = this.rightchild = null; } public SearchBinaryTreenode (t da, suchBinaryTreenode <t> links, SearchBinaryTreenode <T> rechts) {this.data = da; this.leftchild = links; this.rightChild = rechts; } public t getData () {returndaten; } public void setData (t data) {this.data = data; } public SearchBinaryTreenode <T> getleftChild () {return lutchild; } public void setLeftchild (suchBinaryTreenode <T> linkSchild) {this.leftchild = linkChild; } public SearchBinaryTreenode <T> getRightChild () {return RightChild; } public void setrightChild (suchBinaryTreenode <T> rightChild) {this.rightChild = rightChild; } public boolean isleaf () {if (this.leftchild == null && this.rightchild == null) {return true; } return false; }}Implementierung eines binären Suchbaums
Package SearchBinaryTree; Public Class SearchBinaryTree <T> {SearchBinaryTreenode <T> root; public boolean isempty () {if (root == null) {return true; } return false; } public void Visit (SearchBinaryTreenode <T> root) {if (root == null) {System.out.println ("Dieser Baum ist leer!"); } System.out.println (root.getData ()); } public SearchBinaryTreenode <T> getRoot () {if (root == null) {root = new SearchBinaryTreenode <t> (); } return root; } public SearchBinaryTree () {this.root = null; } /** Erstellen Sie einen binären Baum* / public void createTree (SearchBinaryTreenode <T> Knoten, t data) {if (root == null) {root = new SearchBinaryTreenode <t> (); } else {if (math.random ()> 0.5) {// Erstellen Sie einen binären Baum auf zufällige Weise if (node.leftchild == null) {node.leftchild = new SearchBinaryTreenode <t> (Daten); } else {createTree (node.leftchild, data); }} else {if (node.rightchild == null) {node.rightchild = new SearchBinaryTreenode <T> (Daten); } else {createTree (node.rightChild, data); }}}}} /** Suchen im zweiten Suchbaum* / public SearchBinaryTreenode <T> such (suchBinaryTreenode <T> root, t -Wert) {SearchBinaryTreenode <T> current = root; while ((root! = null) && (current.getData ()! Im tatsächlichen Gebrauch können wir gemeinsame Datentypen verwenden, um dieses Generikum zu ersetzen, sodass keine Fehler vorliegen. Current = (value <current.getData ()? Suche (current.leftchild, value): such (current.rightChild, value)); } Return Current; } public SearchBinaryTreenode <T> InsertNode (t -Wert) {SearchBinaryTreenode <T> p = root, pre = null; while (p! = null) {pre = p; // Es ist zu beachten, dass Generika in Java die Größen nicht vergleichen können. Im tatsächlichen Gebrauch können wir gemeinsame Datentypen verwenden, um dieses Generikum zu ersetzen, damit keine Fehler vorliegen, wenn (p.getData () <Wert) {p = P.RightChild; } else {p = P.Leftchild; }} if (root == null) {root = new SearchBinaryTreenode <T> (Wert); } else if (pre.getData () <value) {pre.rightchild = new SearchBinaryTreenode <T> (Wert); } else {pre.leftchild = new SearchBinaryTreenode <t> (Wert); }} /** Zusammenführen und löschen* / public void deleteBymerging (suchBinaryTreenode <T> Knoten) {SearchBinaryTreenode <T> temp = node; if (node! } else if (node.leftchild == null) {// Wenn der gelöschte Knoten keinen linken Unterbaum hat, verwenden Sie den linken Knoten mit der Wortzahl anstelle des gelöschten Knotens node = node.rightchild; } else {// Wenn die linken und rechten Teilbäume der gelöschten Knoten temp = node.leftchild haben; while (temp.rightChild! = null) {temp = temp.rightChild; // Finden Sie den rechten Knoten des linken Subtree} // den rechten Zeiger des gefundenen Knotens dem Wurzel des rechten Teilbaums des gelöschten Knotens temp.rightchild = node.rightChild zuweisen; temp = node; node = node.leftchild; } temp = null; }} / * * Kopieren und löschen * / public void deleteByCoping (SearchBinaryTreenode <T> Knoten) {SearchBinaryTreenode <T> pre = null; SucheBinaryTreenode <T> temp = node; // Wenn der gelöschte Knoten keinen rechten Unterbaum hat, verwenden Sie den Stammknoten seines linken Unterbaums, um den gelöschten Knoten zu ersetzen, wenn (knoten.rightchild == null) {node = node.leftchild; } else if (node.leftchild == null) {node = node.rightChild; } else {// Wenn die linken und rechten Teilbäume der gelöschten Knoten temp = node.leftchild haben; pre = node; while (temp.rightChild! = null) {pre = temp; temp = temp.rightChild; // Reisen Sie, um den linken Knoten des linken Subtree} node zu finden.data = temp.data; // Die Zuordnungsoperation durchführen if (pre == node) {pre.leftchild = node.leftchild; } else {pre.rightchild = node.rightChild; }} temp = null; }}Testklasse
Package SearchBinaryTree; public class SearchBinaryTreetest {public static void main (string [] args) {searchBinaryTree <Integer> tree = new SearchBinaryTree <GanzEger> (); für (int i = 1; i <10; i ++) {tree.createtree (new SearchBinaryTreenode <GanzEger> (), i); } // suche tree.search (tree.root, 7); // Tree zusammenführen und löschen. // Tree kopieren und löschen. }}Ok, das war's!
Der obige Artikel Java erstellt einen binären Suchbaum und implementiert Such-, Einfügungs- und Löschvorgangsbeispiele sind alle Inhalte, die ich mit Ihnen teile. Ich hoffe, Sie können Ihnen eine Referenz geben und ich hoffe, Sie können wulin.com mehr unterstützen.