Maîtrisez l'algorithme de profondeur d'abord de l'arborescence JavaScript dans un seul article

Qu'est-ce qu'un arbre ?

Dans la vraie vie, je crois que tout le monde connaît les arbres. Qu'il s'agisse de saules, de peupliers ou de pêchers, on peut dire que les arbres peuvent être vus partout dans notre vie, les arbres sont une abstraction ; d'un modèle de structure hiérarchique ,

comme indiqué ci-dessous :

Il existe de nombreuses applications de la structure arborescente. Par exemple, la structure organisationnelle d'une entreprise peut être représentée par un arbre, comme indiqué ci-dessous :

En plus des structures organisationnelles, des éléments tels que les arbres généalogiques, les provinces et les villes, etc. peuvent être représentés à l'aide de structures arborescentes.

Terminologie des arbres

Il existe de nombreux termes pour les arbres, comme indiqué ci-dessous :

• Arbre : un ensemble fini de n (n≥0) nœuds Lorsque n=0 , on parle d'arbre vide ;
• degré de nœud : le nombre de sous-arbres d'un nœud par exemple, le degré du nœud B est 2. le degré du nœud A est 3 ;
• le degré de l'arbre : le degré maximum parmi tous les nœuds de l'arbre. Par exemple, dans la figure ci-dessus, le degré du nœud
• feuille est 3 : un nœud de degré 0 ; , également appelé nœud feuille ;
• nœud enfant : comme indiqué dans la figure ci-dessus ;
• nœud frère : comme indiqué dans l'image ci-dessus ;
• nœud racine : comme indiqué dans l'image ci-dessus
• : le niveau maximum parmi tous les nœuds de l'arborescence ; par exemple, la profondeur de l'arborescence dans l'image ci-dessus est de 3 ;
• niveau du nœud : par exemple, le niveau du nœud E est 3, et le niveau du nœud est le niveau du nœud parent + 1, le niveau du nœud racine est 1. ;
• chemin : le canal d'un noeud à un autre noeud , Par exemple, le chemin de A→H est ADH
• longueur du chemin : la distance d'un noeud à un autre noeud , Comme le chemin de A→H C'est 3.

La structure arborescente en JavaScript

peut être considérée comme l'une des structures de données les plus courantes dans le front-end, comme l'arborescence DOM, la sélection en cascade, les composants d'arborescence, etc.

JavaScript ne fournit pas la structure de données arborescente, mais nous pouvons l'utiliser. objets et Array pour simuler un arbre,

comme le code suivant :

const tree = {
  valeur : 'A',
  enfants: [
    {
      valeur : 'B',
      enfants: [
        { valeur : 'E', enfants : null },
        { valeur : 'F', enfants : null },
      ],
    },
    {
      valeur : 'C',
      enfants : [{ valeur : 'G', enfants : null }],
    },
    {
      valeur : 'D',
      enfants: [
        { valeur : 'H', enfants : null },
        { valeur : 'Je', enfants : null },
      ],
    },
  ],
}

Avantages des algorithmes de parcours en largeur et en profondeur.

Profondeur d'abord

L'algorithme de parcours dit en profondeur consiste à rechercher les branches de l'arbre aussi profondément que possible. Son ordre de parcours est le suivant :

L'idée d'implémentation est la suivante :

• visitez le nœud racine ;
• continuez la traversée en profondeur (récursivité) des children du nœud racine ;

le code d'implémentation est le suivant :

function dfs(root) {
  console.log(racine.valeur)
  root.children && root.children.forEach(dfs) // Conformément à ce qui suit // if (root.children) {
  // root.children.forEach(enfant => {
  //dfs(enfant)
  // })
  // }
}
dfs(tree) //Cet arbre est l'arbre défini précédemment/* Résultat A
B
E
F
C
G
D
H
je
*/

Comme vous pouvez le constater, la commande est conforme à la photo, ce qui signifie qu'il n'y a aucun problème avec notre algorithme.

Priorité de largeur

La soi-disant priorité de largeur consiste à visiter les nœuds les plus proches du nœud racine dans l'ordre. Son ordre de parcours est le suivant :

L'idée de mise en œuvre est la suivante :

• créez une file d'attente, ajoutez le nœud racine à la file d'attente ;
• retirez la tête de file d'attente et accédez-y ;
• ajoutez children de la tête de file d'attente à la file d'attente dans l'ordre,
• répétez les étapes 2 et 3
 ;
• la file d'attente est vide.

Le code d'implémentation est le suivant :

function bfs(root) {
  // 1. Créez une nouvelle file d'attente et ajoutez des nœuds à la file d'attente const q = [root]
  // 4 Répétez while (q.length > 0) {
    const node = q.shift() // 2 têtes de file d'attente sont retirées de la file d'attente console.log(node.value)
    // 3 enfants, le chef de l'équipe, sont ajoutés à l'équipe node.children &&
      node.children.forEach(enfant => {
        q.push (enfant)
      })
  }
}
bfs(arbre)
/* Résultat A
B
C
D
E
F
G
H
je
*/

Comme vous pouvez le constater, la commande est conforme à la photo, ce qui signifie qu'il n'y a aucun problème avec notre algorithme.