Este artículo describe los algoritmos transversales transversales y de amplitud de profundidad que implementan un árbol binario en Java. Compártelo para su referencia, como sigue:
1. Análisis
La práctica común de la no recursividad de la cadena de profundidad primero de los árboles binarios es adoptar una pila, y la práctica común de la no recursividad de la transversal de amplitud primero es adoptar una cola.
Caborraje de la primera profundidad : cada ruta de rama posible se puede penetrar hasta que no pueda ser más profundo, y cada nodo solo se puede acceder una vez. Cabe señalar que el recorrido de profundidad del árbol binario es bastante especial y puede subdividirse en el recorrido por adelantado, el recorrido intermedio y la transversal posterior. La descripción específica es la siguiente:
Primer orden transversal : para cualquier subárbol, primero acceda a la raíz, luego atraviese su subárbol izquierdo y finalmente atraviese su subárbol derecho.
Orden medio transversal : para cualquier subárbol, primero atraviese su subárbol izquierdo, luego acceda a la raíz y finalmente atraviesa su subárbol derecho.
Traversal posterior al pedido : para cualquier subárbol, primero atraviese su subárbol izquierdo, luego atraviese su subárbol derecho y finalmente acceda a la raíz.
Apretado de la amplitud : también conocida como jerarquía, accediendo a cada capa de arriba a abajo a su vez. En cada capa, acceda a nodos de izquierda a derecha (o de derecha a izquierda). Después de acceder a una capa, ingresará la siguiente capa hasta que no haya nodos a los que se pueda acceder.
2. Dar ejemplos
El árbol de clasificación binario que se muestra en la siguiente figura requiere el uso de anticipación de pedido anticipado (recursivo, no recursivo), transversal en orden (recursivo, no recursivo), transversal posterior (recursivo, no recursivo) y transversal.
① Código de referencia
paquete binarytreetRaversetest; import java.util.linkedList; import java.util.queue;/** * Deporte prioridad Traversal y amplia prioridad Traversal de árboles binarios * @author fantasy * @version 1.0 2016/05 - 2016/10/07 */clase public BinarySorttree <integer> tree = new BinarySorttree <Integer> (); árbol.insertnode (35); árbol.insertnode (20); árbol.insertnode (15); árbol.insertnode (16); árbol.insertnode (29); árbol.insertnode (28); árbol.insertnode (30); árbol.insertnode (40); árbol.insertnode (50); árbol.insertnode (45); árbol.insertnode (55); System.out.print ("Preordrade traversal (recursivo):"); Tree.Preordertraverse (tree.getroot ()); System.out.println (); System.out.print ("Traversal en orden (recursivo):"); árbol.inordertraverse (tree.getroot ()); System.out.println (); System.out.println (); System.out.print ("Traversal posterior al pedido (recursivo):"); Tree.PostOrderTraverse (tree.getRoot ()); System.out.println (); System.out.print ("Traversal precursivo (no recursivo):"); árbol.preordertraversenorecursion (tree.getroot ()); System.out.println (); System.out.print ("Traversal en orden (no recursivo):"); árbol.inordertraversenorecursion (tree.getroot ()); System.out.println (); System.out.println (); System.out.print ("Traversal posterior al orden (no recursivo):"); Tree.PostOrderTraversenorecursion (tree.getroot ()); System.out.println (); System.out.print ("Brewthpriority Traversal:"); árbol.breadthfirsttraververse (tree.getroot ()); }}/*** nodo*/class nodo <e extiende comparable <e>> {e valor; Nodo <E> izquierda; Nodo <E> derecho; Nodo (valor e) {this.Value = value; izquierda = nulo; recto = nulo; }}/** * Use una secuencia precedente para construir un árbol de clasificación binario (también conocido como árbol de búsqueda binario) */class binarySorttree <e extiende comparable <e>> {nodo privado <E> root; BinarySorttree () {root = null; } public void InsertNode (e value) {if (root == null) {root = new nodo <E> (valor); devolver; } Nodo <E> currentNode = root; while (true) {if (value.compareto (currentNode.Value)> 0) {if (currentNode.right == null) {currentNode.right = new Node <E> (valor); romper; } currentNode = currentNode.right; } else {if (currentNode.left == null) {currentNode.left = new Node <E> (valor); romper; } currentNode = currentNode.left; }}} nodo público <E> getRoot () {return root; } / ** * PRESERDO Traversal del árbol binario (recursivo) * @param nodo * / public void PreorderTraverse (nodo <E> nodo) {system.out.print (node.value + ""); if (node.left! = null) preordenTraverse (node.left); if (node.right! = null) preordentraverse (node.right); } / ** * transversal en orden del árbol binario (recursivo) * @param nodo * / public void inOrderTraverse (nodo <E> nodo) {if (node.left! = Null) inOrderTraverse (node.left); System.out.print (node.value + ""); if (node.right! = null) InloDerStraverse (node.right); } / ** * Traversal posterior al pedido del árbol binario (recursivo) * @param nodo * / public void PostOrderTraverse (nodo <E> nodo) {if (node.left! = Null) PostOrderTraverse (nodo.left); if (node.right! = null) PostOrderTraverse (node.right); System.out.print (node.value + ""); } / ** * PRESIDER ORDER ARVERSAL DEL ÁRBOL binario (no recursivo) * @param root * / public void PreorderTraversenorecursion (nodo <E> root) {LinkedList <node <E>> stack = new LinkedList <node <E>> (); Nodo <E> currentNode = null; stack.push (raíz); while (! stack.isempty ()) {currentNode = stack.pop (); System.out.print (currentNode.Value + ""); if (currentNode.right! = null) stack.push (currentNode.right); if (currentNode.left! = null) stack.push (currentNode.left); }} / ** * Traversal en orden del árbol binario (no recursivo) * @param root * / public void inOrderTraversenorecursion (nodo <e> root) {LinkedList <node <e>> stack = new LinkedList <node <E>> (); Nodo <E> currentNode = root; while (currentNode! = null || actualnode = currentNode.left; } currentNode = stack.pop (); System.out.print (currentNode.Value + ""); actualnode = currentNode.right; }} / ** * Traversal posterior al pedido del árbol binario (no recursivo) * @param root * / public void PostOrderTraversenOrecursion (nodo <E> root) {LinkedList <node <e>> stack = new LinkedList <node <E> (); Nodo <E> currentNode = root; Nodo <E> rightNode = null; while (currentNode! = null || actualnode = currentNode.left; } currentNode = stack.pop (); // El nodo actual no tiene el nodo derecho o el nodo anterior (el nodo que se ha salido) es el nodo correcto del nodo actual, entonces el nodo actual se emite mientras (currentNode.right == null || currentNode.right == RightNode) {System.out.print (CurrentNode.Value + ""); RightNode = CurrentNode; if (stack.isempty ()) {return; // salidas raíz, los extremos transversales} currentNode = stack.pop (); } stack.push (currentNode); // Todavía existe el nodo correcto que no atraviesa CurrentNode = currentNode.right; }} / *** Árbol binario Traverse de ancho de la primera, también conocido como árbol binario de transversal jerárquico* @param nodo* / public void BrewThirsttraverse (node <E> root) {Queue <node <E>> Queue = New LinkedList <Node <Endo> ();; Nodo <E> currentNode = null; cola.offer (raíz); while (! queue.isEmpty ()) {currentNode = queue.poll (); System.out.print (currentNode.Value + ""); if (currentNode.left! = null) queue.offer (currentNode.left); if (currentNode.right! = null) queue.offer (currentNode.right); }}}② Resultado de salida
Recorrido por adelantado (recursivo): 35 20 15 16 29 28 30 40 50 45 55
Traversal en el orden (recursión): 15 16 20 28 29 30 35 40 45 50 55
Traversal posterior al orden (recursión): 16 15 28 30 29 20 45 55 50 40 35
Recuerda anticipada (no recursiva): 35 20 15 16 29 28 30 40 50 45 55
Traversal en servicio (no recursivo): 15 16 20 28 29 30 35 40 45 50 55
Traversal posterior (no recursivo): 16 15 28 30 29 20 45 55 50 40 35
Traversal de amplitud prioritaria: 35 20 40 15 29 50 16 28 30 45 55
Para obtener más información sobre los algoritmos de Java, los lectores interesados en este sitio pueden ver los temas: "Estructura de datos Java y tutorial de algoritmo", "Resumen de las puntas de nodo de operación de Java DOM", "Resumen de Java Archivo y TIPS de operación de directorio" y "Summary of Java Cache Operation Tips" TIPS ""
Espero que este artículo sea útil para la programación Java de todos.