Domine o algoritmo de profundidade da estrutura de árvore JavaScript em um artigo

O que é uma árvore?

Na vida real, acredito que todos estão familiarizados com as árvores. Quer sejam salgueiros, choupos ou pessegueiros, pode-se dizer que as árvores podem ser vistas em todas as nossas vidas no mundo da informática. de um modelo hierárquico ,

conforme mostrado abaixo:

Existem muitas aplicações da estrutura em árvore. Por exemplo, a estrutura organizacional de uma empresa pode ser representada por uma árvore, conforme mostrado abaixo:

Além das estruturas organizacionais, itens como árvores genealógicas, províncias e cidades, etc. podem ser representados por meio de estruturas em árvore.

Terminologia de árvore

Existem muitos termos para árvores, conforme mostrado abaixo:

• Árvore : um conjunto finito de n (n≥0) nós Quando n=0 , é chamado de grau de nó de
• árvore vazio : o número de subárvores de um nó. o grau do nó A é É 3;
• o grau
• da árvore : o grau máximo entre todos os nós da árvore. Por exemplo, na figura acima, o grau da árvore é 3;
• , também chamado de nó folha ;
• nó filho
• : conforme mostrado na figura acima;
nó irmão:
• conforme mostrado na imagem acima
• ;
• por exemplo, a profundidade da árvore na imagem acima é 3
• : por exemplo, o nível do nó E é 3 e o nível do nó é o nível do nó pai + 1, o nível do nó raiz é 1; ;
• caminho : o canal de um nó para outro nó , por exemplo, o caminho de A→H é ADH
• ​​comprimento do caminho : a distância de um nó para outro nó , como o caminho de A→H Isso é 3;

a estrutura de árvore em JavaScript

é uma das estruturas de dados mais comuns no front-end, como árvore DOM, seleção em cascata, componentes de árvore, etc.

JavaScript não fornece a estrutura de dados em árvore, mas podemos usar; objetos e Array para simular uma árvore,

como o seguinte código:

const tree = {
  valor: 'A',
  crianças: [
    {
      valor: 'B',
      crianças: [
        {valor: 'E', filhos: nulo},
        {valor: 'F', filhos: nulo},
      ],
    },
    {
      valor: 'C',
      filhos: [{ valor: 'G', filhos: nulo }],
    },
    {
      valor: 'D',
      crianças: [
        {valor: 'H', filhos: nulo},
        {valor: 'I', filhos: null },
      ],
    },
  ],
}

Vantagens dos algoritmos de travessia em largura e profundidade

Primeiro em profundidade

O chamado algoritmo de travessia em profundidade consiste em pesquisar os ramos da árvore o mais profundamente possível. Sua ordem de travessia é a seguinte:

A ideia de implementação é a seguinte:

• visite o nó raiz;
• continue a travessia em profundidade (recursão) dos children do nó raiz,

o código de implementação é o seguinte:

function dfs(root) {;
  console.log(raiz.valor)
  root.children && root.children.forEach(dfs) // Consistente com o seguinte // if (root.children) {
  // root.children.forEach(child => {
  //dfs(filho)
  // })
  // }
}
dfs(tree) //Esta árvore é a árvore definida anteriormente/* Resultado A
B
E
F
C
G
D
H
EU
*/

Como você pode ver, a ordem é consistente com a imagem, o que significa que não há problema com nosso algoritmo.

Prioridade de amplitude

A chamada prioridade de amplitude é visitar os nós mais próximos do nó raiz em ordem. Sua ordem de passagem é a seguinte:

A ideia de implementação é a seguinte:

• Criar uma fila, adicionar o nó raiz à fila,
• retirar o cabeçalho da fila e acessá-lo
• até que
• children do cabeçalho da fila sejam adicionados à fila;
• a fila está vazia.

O código de implementação é o seguinte:

function bfs(root) {
  // 1. Crie uma nova fila e adicione nós à fila const q = [root]
  // 4 Repita enquanto (q.length > 0) {
    const node = q.shift() // 2 cabeças da fila são retiradas da fila console.log(node.value)
    // 3 filhos, o chefe da equipe, são adicionados à equipe node.children &&
      node.children.forEach(filho => {
        q.push(filho)
      })
  }
}
bfs (árvore)
/* Resultado A
B
C
D
E
F
G
H
EU
*/

Como você pode ver, a ordem é consistente com a imagem, o que significa que não há problema com nosso algoritmo.