Esta es una pregunta de entrevista común, como obtener el recorrido jerárquico del árbol binario a través del pedido anticipado y el recorrido en servicio del árbol binario, etc.
Preorden + orden medio -> construir
Supongamos que ahora hay un árbol binario, como sigue:
En este momento, el orden transversal es:
Preorden: Gdafemhz Inorder: Adefghmz Postorder: AEFDHZMG
Ahora dé un pedido anticipado y en pedido (en orden), cree un árbol binario o entregue el pedido (en orden) y posterior al pedido (PostOder), cree un árbol binario, en realidad es el mismo
Definición de nodo de árbol:
Árbol de clases {char val; árbol izquierda; árbol a la derecha; árbol (char val, árbol izquierdo, árbol a la derecha) {this.val = val; this.left = left; this.right = right;} tree () {} árbol (char val) {this.val = val; this.left = null; this.right = null;}}Hacer logros:
Public Static Tree Builttree (char [] preorden, char [] inorder) {// preorden es la secuencia de pedido preorden // inorder es la secuencia media if (preorden == null || preorden.length == 0) {return null;} árbol root = new Tree (preorden [0]); // Encuentra la posición de la raíz en el orden intindex = 0; for (char i = 0; i <inorder.length; i ++) {if (inorder [i] == root.val) {inOrderIndex = i;}} // el subtree y el sujecito de la izquierda y el subtree de preorden de preorden [] preordensft = Arrays.CopyOfRange (preorden, 1, 1+Inorderindex); Char [] preorden = preordens.copiar (acoplando, ctopopia (preorden (preordera (preordera (preordener 1+inOrderIndex, preorden.length); // la parte subárbol izquierda y subárbol derecha de Inorder char [] inOrderSft = arrays.copyOfRange (inorder, 0, inOrderIndex); char [] inloderright = arrays.copyOfrange (inOrder, inOrderIndex+1, ororder.length); // buildtree (preordenleft, inOrderleft); árbol rightchild = buildtree (preordenRight, inorderright); root.left = leftchild; root.right = rightchild; return root;}En realidad, es lo mismo crear un orden medio + post-pedido. No lo escribiré aquí
Varios recorridos
Transversal posterior a
public static void PostOrderPrint (Root de árbol) {// Traversal posterior // raíces izquierda izquierda y derecha if (root.left! = null) {PostOrderPrint (root.left); } if (root.right! = null) {PostOrderPrint (root.right); } System.out.print (root.val + ""); }Aprenda de un ejemplo y el pedido es el mismo que el orden en el medio. No lo escribiré aquí
Transversal de secuencia de capa
Puede usar una cola de cola para agregar primero el nodo raíz a la cola. Cuando la cola no esté vacía, tome el nodo del nodo del encabezado de la cola e imprima el valor del nodo del nodo. Si los niños izquierdo y derecho del nodo no están vacíos, agregue los niños izquierdo y derecho a la cola.
public static void layerOrderPrint (raíz de árbol) {if (root == null) {return; } // Sequencia de capa Traversal Queue <RERE> qe = new LinkedList <RERE> (); qe.add (raíz); while (! Qe.isEmpty ()) {árbol de árbol = qe.poll (); System.out.print (node.val + ""); if (node.left! = null) {qe.add (node.left); } if (node.right! = null) {qe.add (node.right); }}}Profundidad y prioridad
De hecho, es solo un dicho diferente. La prioridad de profundidad es el recorrido por adelantado, la prioridad de la amplitud es el recorrido por orden.
Public static void DeepFirstPrint (Root de árbol) {// El recorrido de prioridad profunda es equivalente a preordenar el recorrido // por lo que puede usar directamente el traversal preordenado if (root == null) {return; } System.out.print (root.val + ""); if (root.left! = null) {DeepFirstPrint (root.left); } if (root.right! = null) {DeepFirstPrint (root.right); }} public static void profirstprintnonerec (raíz de árbol) {// La forma no recursiva de profundidad prioridad transversal if (root == null) {return; } Pila <bree> st = new Stack <ree> (); St.Add (raíz); while (! St.isEmpty ()) {árbol de árbol = St.Pop (); System.out.print (node.val + ""); // La pila está de vuelta y primero out // agregue el niño derecho primero y luego el niño izquierdo if (node.right! = Null) {st.add (node.right); } if (node.left! = null) {St.add (node.left); }}}Función principal:
public static void main (string [] args) {char [] preorden = "Gdafemhz" .toCarArray (); char [] inorder = "adefghmz" .toCarArray (); Árbol root = main.buildtree (preorden, inorder); // main.postOrderprint (root); // PostOrder Traversal // Main.LayerOrderPrint (root); // secuencia de capa traversal // main.deepfirstprint (raíz); // Traversal de prioridad profunda // main.deepfirstprintnonerec (root); // La versión no recursiva de la Primera Derción de Traversal}Resumir
Lo anterior tiene que ver con el establecimiento de árboles binarios y varios códigos de instancia transversales en Java. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a este sitio:
" Introducción a dos métodos de reflejo en los árboles binarios de programación de Java "
" El lenguaje Java describe la profundidad y el ancho del árbol binario "
Java Binary Tree Rath and Code Ejemplo
Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!