Binärer Sortierbaum wird auch binärer Suchbaum bezeichnet. Es ist entweder ein leerer Baum oder ein binärer Baum mit den folgenden Eigenschaften:
① Wenn der linke Teilbaum nicht leer ist, sind die Werte aller Knoten am linken Subtree kleiner als die Werte seines Wurzelknotens;
② Wenn der rechte Teilbaum nicht leer ist, sind die Werte aller Knoten am rechten Teilbaum größer als die Werte seines Wurzelknotens;
③Die linke und rechte Unterbäume sind auch binäre Sortierbäume.
Der folgende Code implementiert:
import Java.util.linkedList; Import Java.util.queue; Klasse -Knoten {public int data; öffentlicher Knoten übrig; öffentlicher Knoten recht; öffentlich int linksgerechnet; public int rightmaxDistance; public node (int data) {this.data = data; this.left = null; this.right = null; }}/*** @Author Ty* Implementieren eines binären Sortierbaums, einschließlich Insertion, In-Ordnung-Traversal, Vorbestellungen, Traversal, Nachauftrags-Traversal und Berechnung der maximalen Distanz aller Knoten*/Public Class BinaryTree {private Knoten Root; public BinaryTree () {root = null; } public void Insert (int data) {node newnode = new node (data); if (root == null) root = newnode; sonst {Knoten current = root; Knoten übergeordnet; while (true) {// Suchen Sie die Position übergeordnet = Strom; if (Data <current.data) {current = current.left; if (current == null) {parent.left = newnode; zurückkehren; }} else {current = current.right; if (current == null) {parent.right = newnode; zurückkehren; }}}}}}} // numerische Werte eingeben, um einen binären Baum public void buildtree (int [] data) {for (int i = 0; i <data.length; i ++) {Insert (data [i]) zu erstellen; }}} // In-Ordnung-Traversal-Methode implementiert rekursiv öffentliches void in Order (Knoten localroot) {if (localroot! = Null) {inOrder (localroot.left); System.out.print (localroot.data+""); in Ordnung (Localroot.Right); }} public void inOrder () {this.inorder (this.root); } // Die vorbestellte Traversalmethode implementiert rekursiv öffentliche void vorbestellt (Knoten localroot) {if (localroot! = Null) {System.out.print (localroot.data+"); Vorbestellung (Localroot.Left); Vorbestellung (Localroot.Right); }} public void vorbestellt () {this.preorder (this.root); } // Die Postorder -Traversal -Methode implementiert die öffentliche void -Postorder (Knoten localroot) {if (localroot! = Null) {postorder (localroot.left); Postorder (Localroot.Right); System.out.print (localroot.data+""); }} public void postorder () {this.postorder (this.root); } /*** Layer-Sequence-Traversal-Binärbaum: Geben Sie nun den Wurzelknoten in die Warteschlange ein und nehmen Sie dann jedes Mal einen Knoten aus der Warteschlange, um den Wert des Knotens zu drucken. * Wenn dieser Knoten einen untergeordneten Knoten hat, legen Sie seinen untergeordneten Knoten in den Schwanz der Warteschlange, bis die Warteschlange leer ist Queue <node> q = new LinkedList <node> (); Q.Add (this.root); while (! q.isempty ()) {node n = q.poll (); System.out.print (n.data+""); if (n.left! = null) Q.Add (N.Left); if (n.right! = null) q.add (n.right); }} private int maxlen = 0; private int max (int a, int b) {return a> b? a: b; } public void findMaxDistance (Knotenwurzel) {if (root == null) return; if (root.left == null) root.leftmaxDistance = 0; if (root.right == null) root.rightMaxDistance = 0; if (root.left! = null) findMaxDistance (root.left); if (root.right! = null) findMaxDistance (root.Right); // Berechnen Sie den maximalen Abstand vom Wurzelknoten im linken Wortbaum, wenn (root.left! // Berechnen Sie den maximalen Abstand vom Wurzelknoten im rechten Wortbaum, wenn (root.right! // Erhalten Sie den maximalen Abstand aller Knoten des binären Baums, wenn (Root.leftmaxDistance+root.rightMaxDistance> maxlen) {maxlen = root.leftmaxDistance+root.rightMaxDistance; }} public static void main (String [] args) {binaryTree bitree = new BinaryTree (); int [] data = {2,8,7,4,9,3,1,6,7,5}; bitree.buildtree (Daten); System.out.print ("In-Ordnung-Traversal von Binärbaum:"); bitree.inorder (); System.out.println (); System.out.print ("Vorbestellungen von Binärbaum:"); bitree.preorder (); System.out.println (); System.out.println (); System.out.println (); System.out.print ("Post-Order-Traversal von Binärbaum:"); bitree.postorder (); System.out.println (); System.out.print ("Schichtreihenreihe von Binärbaum:"); bitree.layertranverse (); System.out.println (); bitree.findMaxDistance (bitree.root); System.out.println ("Maximale Entfernung der Knoten im binären Baum:"+bitree.maxlen); }}Das obige ist der gesamte Inhalt dieses Artikels. Ich hoffe, dass der Inhalt dieses Artikels für das Studium oder die Arbeit eines jeden hilfreich sein wird. Ich hoffe auch, Wulin.com mehr zu unterstützen!