En la vida de programación, siempre encontramos estructuras de árboles. En los últimos días, solo necesitamos operar la estructura del árbol, por lo que registramos nuestros propios métodos y procesos de operación. Ahora suponga que hay un árbol como este (no importa si es un árbol binario o no, los principios son los mismos)
1. Prioridad de profundidad
La abreviatura inglesa es DFS, a saber, la primera búsqueda de profundidad.
La búsqueda de profundidad primero es un método que se usa más comúnmente en las primeras etapas de los rastreadores de desarrollo. Su propósito es llegar a los nodos de la hoja de la estructura buscada (es decir, aquellos archivos HTML que no contienen hipervínculos). En un archivo HTML, cuando se selecciona un hipervínculo, el archivo HTML vinculado realizará una búsqueda de profundidad primero, es decir, se debe buscar una cadena separada en su totalidad antes de buscar los resultados de hipervínculo restantes. La búsqueda de prioridad de profundidad sigue al hipervínculo en el archivo HTML hasta que no se puede profundizar más, luego regresa a un cierto archivo HTML y continúa seleccionando otros hipervínculos en el archivo HTML. Cuando no hay otros hipervínculos disponibles, la búsqueda ha terminado. El proceso es simplemente profundizar en cada ruta de rama posible hasta que no pueda ser más profundo, y cada nodo solo se puede acceder una vez. Para el ejemplo anterior, el resultado del recorrido de profundidad primero es: A, B, D, E, I, C, F, G, H. (suponiendo que el lado izquierdo del nodo infantil se deja primero).
La prioridad de profundidad se utiliza para atravesar cada nodo, y se requiere una estructura de datos como un montón. La característica de la pila es entrar primero y luego salir. Todo el proceso de recorrido es el siguiente:
Primero, presione el nodo A en el montón, pila (a);
Pensar el nodo A y presione los nodos infantiles C y B en el montón al mismo tiempo. En este momento, B está en la parte superior del montón, Stack (B, C);
Pensar el nodo B y presione los nodos infantiles de B E y D en el montón. En este momento, D está en la parte superior del montón, pila (d, e, c);
Nodo emergente D, no se presionan nodos infantiles y E está en la parte superior del montón, pila (e, c);
Pop Up Up Node e y presione el nodo infantil I en la pila (i, c);
... a su vez, y se completa el recorrido final. El código Java es más o menos como sigue:
public void profundidadFirst () {pila <map <string, object >> nodestack = new Stack <map <string, object >> (); map <string, object> node = new HashMap <String, Object> (); nodestack.Add (nodo); while (! Nodestack.isEmpty ()) {node = nodestack.pop (); system.out.println (nodo); // Obtenga el nodo infantil del nodo. Para el árbol binario, es obtener el nodo infantil izquierdo y el nodo infantil derecho de la lista de nodos <map <string, object >> children = getChildren (node); if (niños! = Null &&! Children.isempty ()) {para (map child: children) {nodestack.push (niño);}}}} // nodos se almacenan usando maps utilizando el mapa usando el mapa utilizando el mapa utilizando el map2. Prioridad
La abreviatura inglesa es BFS, lo que significa amplitud de FirstSearch. Según la prueba del proceso, se accede a cada capa de nodos a su vez, y después de acceder a una capa, cada nodo solo puede acceder a ella una vez. Para el ejemplo anterior, el resultado de la primera transversal es: A, B, C, D, E, F, G, H, I (suponiendo que se acceda a cada capa de nodos de izquierda a derecha).
Se utiliza la prioridad de amplitud para atravesar cada nodo, y se requiere una estructura de datos como una cola. La característica de la cola es la primera entrada, y, de hecho, también puede usar una cola de doble extremo. La diferencia es que los nodos se pueden insertar y aparecer en la primera posición de la cola de doble extremo. Todo el proceso de recorrido es el siguiente:
Primero inserte el nodo A en la cola, cola (a);
Nodo emergente A e inserte los nodos infantiles B y C de A en la cola. En este momento, B está al comienzo de la cola y C está al final de la cola, cola (b, c);
Pense el nodo B e inserte los nodos infantiles D y E de B en la cola al mismo tiempo. En este momento, C está al comienzo de la cola y E está al final de la cola, cola (c, d, e);
Nodo emergente C e inserte los nodos infantiles F, G, H de C en la cola. En este momento, D está a la cabeza de la cola y H está al final de la cola, cola (d, e, f, g, h);
El nodo emergente D, D no tiene nodos infantiles, en este momento E está a la cabeza de la cola, h está en la cola de la cola, cola (e, f, g, h);
... a su vez, y se completa el recorrido final. El código Java es más o menos como sigue:
public void Breadfirst () {deque > nodedeque = new Arraydeque > (); Mapa nodo = nuevo hashmap (); nodedequ.add (nodo); while (! Nodedeque.isEmpty ()) {node = nodedequ.peekfirst (); System.out.println (nodo); // Obtener el nodo infantil del nodo. Para el árbol binario, el nodo hijo izquierdo y el nodo infantil derecho del nodo deben obtener la lista del nodo. > niños = GetChildren (nodo); if (children! = null &&! children.isempty ()) {para (map child: children) {nodedequ.add (niño); }}}} // La cola de doble extremo se usa aquí, que es lo mismo que usar cola Resumir
Lo anterior es todo el contenido de este artículo sobre los ejemplos de código de implementación de Java de profundidad y amplio primero, y espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!