Освойте алгоритм обработки глубины древовидной структуры JavaScript в одной статье

Что такое дерево?

Я считаю, что в реальной жизни каждый знаком с деревьями. Будь то ивы, тополя или персиковые деревья, можно сказать, что в компьютерном мире деревья можно увидеть повсюду, деревья — это абстракция ; иерархической структуры ,

как показано ниже:

Существует множество применений древовидной структуры. Например, организационную структуру компании можно представить в виде дерева, как показано ниже:

Помимо организационных структур, такие вещи, как генеалогические деревья, провинции, города и т. д., могут быть представлены с использованием древовидных структур.

Терминология деревьев

Существует множество терминов для обозначения деревьев, как показано ниже:

• Дерево : конечное множество из n (n≥0) узлов. Когда n=0 , оно называется пустым деревом;
• степень узла : количество поддеревьев узла. Например, степень узла B равна 2, а степень узла равна 2. степень узла A равна 3;
• степень дерева : максимальная степень среди всех узлов дерева. Например, на приведенном выше рисунке степень конечного узла равна 3:
• узел со степенью 0; , также называемый листовым узлом ;
• дочерний узел : как показано на рисунке выше;
• родственный узел : как показано на рисунке выше;
• корневой узел : как показано на рисунке выше;
• максимальный уровень среди всех узлов в дереве , например, глубина дерева на рисунке выше равна 3;
• уровень узла : например, уровень узла E равен 3, а уровень узла — это уровень родительского узла + 1, уровень корневого узла — 1. ;
• путь : канал от одного узла к другому узлу , например, путь A→H — ADH ;
• длина пути : расстояние от одного узла до другого узла , например путь A→H. Это 3.

древовидная структура в JavaScript

является одной из наиболее распространенных структур данных во внешнем интерфейсе, например дерево DOM, каскадный выбор, компоненты дерева и т. д.

JavaScript не предоставляет древовидную структуру данных, но мы можем ее использовать; объекты и массив для имитации дерева,

например следующий код:

const Tree = {
  значение: 'А',
  дети: [
    {
      значение: 'Б',
      дети: [
        {значение: 'E', дети: ноль},
        {значение: 'F', дети: ноль},
      ],
    },
    {
      значение: 'С',
      дети: [{ значение: 'G', дети: ноль }],
    },
    {
      значение: 'D',
      дети: [
        {значение: 'H', дети: ноль},
        {значение: 'Я', дети: ноль},
      ],
    },
  ],
}

Преимущества алгоритмов обхода в ширину и в глубину.

В глубину

Так называемый алгоритм обхода в глубину предназначен для максимально глубокого поиска ветвей дерева. Его порядок обхода следующий:

Идея реализации следующая:

• посетить корневой узел;
• продолжить обход (рекурсию) children корневого узла,

код реализации следующий:

function dfs(root) {;
  console.log(root.value)
  root.children && root.children.forEach(dfs) // Соответствует следующему // if (root.children) {
  // root.children.forEach(child => {
  //dfs(дочерний)
  // })
  // }
}
dfs(tree) //Это дерево является деревом, определенным ранее/* Результат A
Б
Э
Ф
С
Г
Д
ЧАС
я
*/

Как видите, порядок соответствует картинке, а значит проблем с нашим алгоритмом нет.

Приоритет ширины.

Так называемый приоритет ширины заключается в посещении узлов, ближайших к корневому узлу, по порядку. Порядок его обхода следующий:

Идея реализации следующая:

• создать очередь, добавить в очередь корневой узел,
• исключить из очереди голову очереди и получить к ней доступ
• children головы очереди последовательно
• повторять шаги 2 и 3
;
• очередь пуста.

Код реализации следующий:

function bfs(root) {
  // 1. Создать новую очередь и добавить в нее узлы const q = [root]
  // 4 Повторяем while (q.length > 0) {
    const node = q.shift() // 2-й заголовок очереди выводится из очереди console.log(node.value)
    // В команду добавляются 3 ребенка, глава команды node.children &&
      node.children.forEach(child => {
        q.push(ребенок)
      })
  }
}
bfs(дерево)
/* Результат А
Б
С
Д
Э
Ф
Г
ЧАС
я
*/

Как видите, порядок соответствует картинке, а значит проблем с нашим алгоритмом нет.