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

Cet article vous apporte des connaissances pertinentes sur javascript, présentant principalement l'algorithme de profondeur de structure arborescente JavaScript. La structure arborescente peut être considérée comme l'une des structures de données les plus courantes dans le front-end, telles que l'arborescence DOM et la cascade. selection., composant d'arborescence, jetons-y un coup d'œil, j'espère que cela sera utile à tout le monde.

【Recommandations associées : tutoriel vidéo javascript, front-end web】

Qu'est-ce qu'un arbre

Dans la vraie vie, je pense que tout le monde connaît les arbres, qu'il s'agisse de saules, de peupliers ou de pêchers. arbres , on peut dire que les arbres peuvent être vus partout dans nos vies ; dans le monde informatique, un arbre est un modèle abstrait d'une structure hiérarchique. Par exemple, la structure organisationnelle d'une entreprise peut être représentée par un arbre, comme illustré. ci-dessous :

En plus de la structure organisationnelle, la généalogie, les provinces et villes, etc. peuvent également être représentées par une arborescence.

Terminologie de l'arbre

L'arbre a de nombreux termes, comme indiqué ci-dessous :

Arbre

 : un ensemble fini de n (n≥0) nœuds, lorsque n=0 , on l'appelle un arbre vide ;

Le degré du nœud : le nombre de

sous-arbres

du nœud Par exemple, le degré du nœud B est 2, et 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 l'image ci-dessus, le degré de l'arbre est 3

• nœud feuille : n=0时，称为空树；
• 节点的度：节点的子树个数，例如B节点的度就是2，A节点的度就是3；
• 树的度：树的所有节点中最大的度数，例如上图中，树的度是3；
• 叶子节点：度为0的节点，也叫叶节点；
• 子节点：如上图；
• 兄弟节点：如上图；
• 根节点：如上图；
• 树的深度：树中所有结点中的最大层次，例如上图中树的深度就是3；
• 节点的层次：例如E节点的层次就是3，节点的层次就是父节点层次+1，根节点的层次为1；
• 路径：一个节点到另一个节点的通道，例如A→H的路径就是A D H；
• 路径长度：一个节点到另一个节点的距离，例如A→H的路径就是3。

JavaScript中的树

树结构可以说是前端中最常见的数据结构之一，比如说DOM树、级联选择、树形组件等等；

JavaScript中并没有提供树这个数据结构，但是我们可以通过对象和数组来模拟一个树，

例如下面这段代码：

const tree = {
  value: 'A',
  children: [
    {
      value: 'B',
      children: [
        { value: 'E', children: null },
        { value: 'F', children: null },
      ],
    },
    {
      value: 'C',
      children: [{ value: 'G', children: null }],
    },
    {
      value: 'D',
      children: [
        { value: 'H', children: null },
        { value: 'I', children: null },
      ],
    },
  ],
}

广度优先和深度优点遍历算法

深度优先

所谓的深度优先遍历算法，就是尽可能深的去搜索树的分支，它的遍历顺序如下图：

实现思路如下：

• 访问根节点；
• 对根节点的children持续进行深度优先遍历（递归）；

实现代码如下：

function dfs(root) {
  console.log(root.value)
  root.children && root.children.forEach(dfs) // 与下面一致
  // if (root.children) {
  //   root.children.forEach(child => {
  //     dfs(child)
  //   })
  // }
}
dfs(tree) // 这个tree就是前面定义的那个树
/* 结果
A
B
E
F
C
G
D
H
I
*/

可以看到，和图中的顺序是一致的，也就是说我们的算法没有问题。

广度优先

所谓的广度优先就是依次访问离根节点近的节点，它的遍历顺序如下图：

实现思路如下：

• 创建要给队列，把根节点入队；
• 把队头出队并访问；
• 把队头的childrenun nœud de degré 0, également ; appelé nœud feuille
 ;

nœud enfant

 : comme indiqué dans l'image ci-dessus

Nœuds frères et sœurs

 : comme indiqué dans l'image ci-dessus

Nœud racine : comme indiqué dans l'image ci-dessus ; Profondeur de l'arbre : Le niveau maximum de tous les nœuds de l'arbre

, par exemple, la profondeur de l'arbre dans l'image ci-dessus est de 3 🎜🎜🎜Le niveau du nœud🎜 : Par exemple, le niveau du Le nœud E est 3, le niveau du nœud est 🎜le niveau du nœud parent + 1 et le niveau du nœud racine est 1 🎜🎜🎜🎜Chemin🎜 : 🎜Le canal d'un nœud à un autre nœud 🎜, par exemple, le chemin de A ; →H est A D H ; 🎜🎜🎜Longueur du chemin🎜 : 🎜La distance d'un nœud à un autre nœud🎜, par exemple, le chemin de A→H est 3. 🎜🎜🎜Arbre en JavaScript🎜🎜La structure arborescente 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, le composant arborescent, etc. 🎜🎜La structure de données arborescente est non fourni en JavaScript, mais nous pouvons simuler un arbre à travers des objets et des tableaux, 🎜🎜🎜Par exemple, le code suivant : 🎜🎜

function bfs(root) {
  // 1. 新建队列 跟节点入队
  const q = [root]
  // 4 重复执行
  while (q.length > 0) {
    const node = q.shift() // 2 队头出队
    console.log(node.value)
    // 3 队头 children 依次入队
    node.children &&
      node.children.forEach(child => {
        q.push(child)
      })
  }
}
bfs(tree)
/* 结果
A
B
C
D
E
F
G
H
I
*/

🎜Algorithme de traversée axé sur la largeur et l'avantage en profondeur🎜🎜Profondeur d'abord🎜🎜🎜Le so- appelé algorithme de parcours en profondeur consiste à essayer autant que possible de rechercher profondément les branches de l'arbre. Sa séquence de parcours est la suivante : 🎜🎜🎜🎜🎜🎜L'idée d'implémentation est la suivante : 🎜🎜🎜🎜Visitez le nœud racine ; 🎜🎜Continuez le parcours en profondeur (récursion) de la racine node's children; 🎜🎜🎜🎜Le code d'implémentation est le suivant :🎜🎜rrreee🎜Vous pouvez voir que l'ordre est cohérent avec l'image, 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 suivant : 🎜🎜🎜🎜🎜🎜L'idée d'implémentation est la suivante : 🎜🎜🎜🎜Créez une file d'attente et ajoutez le nœud racine à la file d'attente ; 🎜 🎜Supprimez la tête de file d'attente et accédez-y ; 🎜🎜Ajoutez les enfants en tête de file d'attente dans la file d'attente à tour de rôle ; 🎜🎜Répétez les étapes 2 et 3 jusqu'à ce que la file d'attente soit vide. 🎜🎜🎜🎜Le code d'implémentation est le suivant : 🎜🎜rrreee🎜Comme vous pouvez le voir, il est conforme à l'ordre dans l'image, ce qui signifie qu'il n'y a aucun problème avec notre algorithme. 🎜🎜【Recommandations associées : 🎜tutoriel vidéo javascript🎜, 🎜front-end web🎜】🎜

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!