El árbol de clasificación binario también se llama árbol de búsqueda binaria. Es un árbol vacío o un árbol binario con las siguientes propiedades:
① Si el subárbol izquierdo no está vacío, entonces los valores de todos los nodos en el subárbol izquierdo son más pequeños que los valores de su nodo raíz;
②Se el subárbol correcto no está vacío, entonces los valores de todos los nodos en el subárbol derecho son mayores que los valores de su nodo raíz;
③Los subárboles izquierdo y derecho también son árboles binarios respectivamente.
El siguiente código implementa:
import java.util.linkedList; import java.util.queue; class nodo {public int data; nodo público a la izquierda; Derecho del nodo público; Public int LeftmaxDistance; Public int RightmaxDistance; public nodo (int data) {this.data = data; this.left = null; this.right = null; }}/*** @author ty* Implementación de un árbol de clasificación binario, incluida la inserción, el recorrido en orden, el recorrido por pedido, el recorrido posterior al orden y el calcular de la distancia máxima de todos los nodos*/clase pública BinaryTree {Root de nodo privado; public binaryTree () {root = null; } public void Insert (int data) {nodo newNode = new Node (data); if (root == null) root = newnode; else {nodo corriente = root; Padre nodo; while (true) {// Find Insert Position Parent = Current; if (data <current.data) {current = current.left; if (current == null) {parent.left = newnode; devolver; }} else {current = current.right; if (current == null) {parent.right = newnode; devolver; }}}}}}} // Valores numéricos de entrada para construir un árbol binario public void buildtree (int [] data) {for (int i = 0; i <data.length; i ++) {insert (data [i]); }}} // El método de traversal en orden implementa recursivamente public void inorder (nodo localroot) {if (localroot! = Null) {inorder (localroot.left); System.out.print (localroot.data+""); inorder (localroot.right); }} public void inorder () {this.inorder (this.root); } // El método de traversal de preorden implementa recursivamente Public void Preorder (nodo localroot) {if (localroot! = Null) {system.out.print (localroot.data+""); preorden (localroot.left); preorden (localroot.right); }} public void preorden () {this.Preorder (this.root); } // El método de traversal PostOrder implementa recursivamente public void PostOrder (nodo localRoot) {if (localroot! = Null) {PostOrder (localroot.left); PostOrder (localroot.right); System.out.print (localroot.data+""); }} public void PostOrder () {this.postorder (this.root); } /*** Árbol binario transversal de secuencia de capa: ahora coloque el nodo raíz en la cola y luego tome un nodo de la cola cada vez para imprimir el valor del nodo. * Si este nodo tiene un nodo infantil, coloque su nodo hijo en la cola de la cola hasta que la cola esté vacía*/ public void layertranverse () {if (this.root == null) return; Cola <node> q = new LinkedList <Node> (); Q.Add (this.root); while (! Q.isEmpty ()) {nodo 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; privado int max (int a, int b) {return a> b? a: b; } public void findmaxDistance (root nodo) {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); // Calcule la distancia máxima desde el nodo raíz en el árbol de palabras izquierdo if (root.left! = Null) root.leftmaxDistance = max (root.left.leftmaxdistance, root.left.rightmaxDistance) +1; // Calcule la distancia máxima desde el nodo raíz en el árbol de palabras derecho if (root.right! = Null) root.rightmaxDistance = max (root.right.leftmaxdistance, root.right.rightmaxdistance) +1; // Obtenga la distancia máxima de todos los nodos del árbol binario if (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 (datos); System.out.print ("transversal del árbol binario:"); bitree.inorder (); System.out.println (); System.out.print ("Presente de pedido del árbol binario:"); bitree.preorder (); System.out.println (); System.out.println (); System.out.println (); System.out.print ("Traversal posterior al pedido del árbol binario:"); bitree.postorder (); System.out.println (); System.out.print ("Traversal de orden de capa del árbol binario:"); bitree.layertranverse (); System.out.println (); bitree.findmaxdistance (bitree.root); System.out.println ("Distancia máxima de los nodos en el árbol binario:"+bitree.maxlen); }}Lo anterior es todo el contenido de este artículo. Espero que el contenido de este artículo sea de ayuda para el estudio o el trabajo de todos. ¡También espero apoyar a Wulin.com más!