Domine el algoritmo de profundidad de la estructura de árbol de JavaScript en un artículo

¿Qué es un árbol?

En la vida real, creo que todo el mundo está familiarizado con los árboles, ya sean sauces, álamos o melocotoneros, se puede decir que los árboles se pueden ver en todas partes de nuestras vidas, los árboles son una abstracción ; de una estructura jerárquica ,

como se muestra a continuación:

Existen muchas aplicaciones de la estructura de árbol. Por ejemplo, la estructura organizativa de una empresa se puede representar mediante un árbol, como se muestra a continuación:

Además de las estructuras organizativas, se pueden representar cosas como árboles genealógicos, provincias y ciudades, etc. mediante estructuras de árbol.

Terminología de árboles

Hay muchos términos para árboles, como se muestra a continuación:

• Árbol : un conjunto finito de n (n≥0) nodos. Cuando n=0 , se denomina árbol vacío;
• el número de subárboles de un nodo es 2. el grado del nodo A es 3;
• el grado del árbol : el grado máximo entre todos los nodos del árbol. Por ejemplo, en la figura anterior, el grado del
• nodo de hoja del árbol: un nodo con grado 0; , también llamado nodo hoja ;
• nodo hijo : como se muestra en la figura anterior;
• nodo hermano : como se muestra en la imagen de arriba;
• nodo raíz : como se muestra en la imagen de arriba
• : el nivel máximo entre todos los nodos del árbol ; por ejemplo, la profundidad del árbol en la imagen de arriba es
• el nivel de nodo 3: por ejemplo, el nivel del nodo E es 3, el nivel del nodo es el nivel del nodo principal + 1 y el nivel del nodo raíz es 1; ;
• ruta : el canal de un nodo a otro nodo , por ejemplo, la ruta de A→H es ADH ;
• longitud de la ruta : la distancia de un nodo a otro nodo , como la ruta de A→H Eso es 3.

la estructura de árbol en JavaScript

es una de las estructuras de datos más comunes en el front-end, como el árbol DOM, la selección en cascada, los componentes del árbol, etc.

JavaScript no proporciona la estructura de datos del árbol, pero podemos usarla; objetos y Array para simular un árbol,

como el siguiente código:

const tree = {
  valor: 'A',
  niños: [
    {
      valor: 'B',
      niños: [
        { valor: 'E', hijos: nulo },
        { valor: 'F', hijos: nulo },
      ],
    },
    {
      valor: 'C',
      hijos: [{ valor: 'G', hijos: nulo }],
    },
    {
      valor: 'D',
      niños: [
        { valor: 'H', hijos: nulo },
        { valor: 'yo', hijos: nulo },
      ],
    },
  ],
}

Ventajas de los algoritmos de recorrido en amplitud y profundidad

Primero en profundidad

El llamado algoritmo de recorrido en profundidad primero busca las ramas del árbol lo más profundamente posible. Su orden de recorrido es el siguiente:

La idea de implementación es la siguiente:

• visitar el nodo raíz;
• continuar con el recorrido en profundidad (recursión) de children del nodo raíz;

el código de implementación es el siguiente:

function dfs(root) {
  console.log(valor.raíz)
  root.children && root.children.forEach(dfs) // Consistente con lo siguiente // if (root.children) {
  // root.children.forEach(niño => {
  //dfs(niño)
  // })
  // }
}
dfs(tree) //Este árbol es el árbol definido previamente/* Resultado A
B
mi
F
do
GRAMO
D
h
I
*/

Como puede ver, el orden es consistente con la imagen, lo que significa que no hay ningún problema con nuestro algoritmo.

Prioridad de amplitud

La llamada prioridad de amplitud es visitar los nodos más cercanos al nodo raíz en orden. Su orden transversal es el siguiente:

La idea de implementación es la siguiente:

• cree una cola, agregue el nodo raíz a la cola;
• retire el encabezado de la cola y acceda a él;
• agregue children del encabezado de la cola a la cola en secuencia;
• repita los pasos 2 y 3; la cola está vacía.

El código de implementación es el siguiente:

function bfs(root) {
  // 1. Crea una nueva cola y agrega nodos a la cola const q = [raíz]
  // 4 Repetir mientras (q.length > 0) {
    const node = q.shift() // 2 encabezados de cola se retiran de la cola console.log(node.value)
    // 3 niños, el jefe del equipo, se agregan al equipo node.children &&
      nodo.niños.forEach(niño => {
        q.push(niño)
      })
  }
}
novios (árbol)
/* Resultado A
B
do
D
mi
F
GRAMO
h
I
*/

Como puede ver, el orden es consistente con la imagen, lo que significa que no hay ningún problema con nuestro algoritmo.