предисловие
Однажды я радостно печатал код и услышал, как коллега по соседству бормочет о реализации функции, которая, как подозревается, является запросом древовидных данных. Заинтересованный и жаждущий узнать, я подошел.
Я:Вы выполняете многоуровневый групповой запрос?
коллега:Да, в группе вопросов есть группы вопросов, и идентификатор вопроса помещается в нижнюю группу вопросов.Я хочу инкапсулировать функцию, чтобы найти все идентификаторы вопросов в группе вопросов.
Я:Так есть ли у вас какие-либо планы по его реализации?
коллега:Глядя на эту древовидную структуру данных, я планирую использовать рекурсию, чтобы найти ее слой за слоем.
Я:Это не так.Вы можете учиться на идее глубокого обхода в виде стекирования, и вы можете сделать это в одном цикле.Сложность низкая, код прост для понимания, и стек не взорвется.
коллега:И такая операция? Расскажите о том, как этого добиться?
Затем я взял свой блокнот и ручку и объяснил это своим коллегам...
глубокий обход
Идея глубокого обхода в основном сводится к двум пунктам:
- Начиная с непосещенной вершины, следуйте по краю вершины, чтобы найти непосещенную точку.
- Когда доступная точка не найдена, вернитесь к предыдущей вершине и продолжайте поиск до тех пор, пока не будут посещены все точки.
Проще говоря, это «один путь в темноту, не задев южную стену и не оборачиваясь», что также подчеркивает «глубокий"специальность.
Существуют рекурсивная и нерекурсивная версии глубокого обхода.Эта статья в основном объясняет нерекурсивную версию, используякучаРеализована структура данных, которая характеризуется "первым пришел, последним вышел". При глубинном обходе в качестве вершины-кандидата обычно выбираются последние данные, и стек может использоваться для управления вершиной-кандидатом.
Графический процесс
Как говорится, тысяча слов хуже картинки. Нижеследующее иллюстрируетДеревоа такжекучаизменения для разбора процесса глубокого обхода. Перед этим составляется структура данных.
{
value: 'A',
children: [
{
value: 'B',
children: [
{
value: 'D',
children: [
{
value: 'H',
children: []
}
]
},
{
value: 'E',
children: []
}
]
},
{
value: 'C',
children: [
{
value: 'F',
children: []
},
{
value: 'G',
children: []
}
]
}
]
}
Преобразуйте данные в структуру двоичного дерева следующим образом:
1. Теперь идем из вершины А
A помещается в стек, вершина стека представляет текущую вершину
2. Прокрутите вниз до Б
A выталкивает стек, B и C толкают стек
После того, как A пройден, это означает, что к нему обращались, и его не нужно хранить в стеке, и он извлекается из стека.
Вам может быть интересно, почему B и C помещаются вместе, а не B. Помните, что мы сказали выше: «когда не найдена доступная точка, вернитесь к предыдущей вершине», поэтому нам нужно сначала сохранить ее в стеке. Вершины-кандидаты, которые будут быть пройдена после его завершения, чтобы облегчить последующий возврат для поиска вершин, и C в это время является вершиной-кандидатом. Если вы этого не понимаете, ничего страшного, просто следите за процессом, и вы постепенно поймете. Теперь просто помните, что точка наверху стека является текущей вершиной.
3. Прокрутите вниз до D
Б всплывает стек, d и e толкать стек
4. Прокрутите вниз до Н
D хлопает, H толкает
5. Нет узла вниз, вернуться к предыдущей вершине E
H извлекает стек
6. Нет узла вниз, вернуться к предыдущей вершине C
E выталкивает стек
7. Найдите узел до F
C извлекает стек, F, G толкает стек
8. Нет узла вниз, вернуться к предыдущей вершине G
F извлекает стек
9. Конец обхода
G выталкивает стек, стек пуст, нет узлов для поиска, и весь процесс обхода завершается.
JS достигают
/**
* 深度遍历查找
* @param {*} tree 树形数据
* @param {*} target 想要查找的目标
*/
function DFS (tree, target) {
// 模拟栈，管理结点
let stack = [tree]
while (stack.length) {
// 栈顶节点出栈
let node = stack.pop()
// 查找到目标，退出
if (node.value === target) {
return target
}
if (node.children && node.children.length) {
// 将候选顶点入栈，进行下一次循环
stack.push(...node.children.reverse())
}
}
}
reverseЭто следовать идее глубокого обхода и обхода вниз по краю. Ссылаясь на приведенную выше блок-схему, после прохождения A следующим узлом будет B. Если здесь не выполняется инверсия, непосредственноpush, стек станет[B, C], узел, взятый с вершины стека, будет C.
Решать проблему
Просмотрите проблемы, которые необходимо решить, и найдите вопросы в многоуровневой группе вопросов. Там может быть список групп вопросов и вопросов под каждым слоем групп вопросов. Независимо от того, насколько глубоким является уровень, то, что необходимо, чтобы найти все вопросы в группе вопросов и сохранить их.
Глубинный обход заключается в поиске определенного узла, и при обращении к этой идее для решения вышеупомянутых сценариев необходимо внести некоторые изменения.
- Нет необходимости находить узлы, но весь обход для нахождения подуровня темы, процесс обхода не устанавливает целевое условие завершения
- Нет необходимости навязывать обход по краю, т.е.
reverse - Стек выталкивает данные, к которым осуществляется доступ, из стека, и вам нужно создать еще один массив для хранения необходимых данных.
Получить план:
/**
* 查找题组下的所有题目
* @param {*} tree 树形数据
*/
function findQuestions (tree) {
// 模拟栈，管理结点
let stack = [tree]
let res = []
while (stack.length) {
// 栈顶结点出栈
let node = stack.pop()
// 题组有题目
if (node.question_list && node.question_list.length) {
// 存储需要的数据
res.push(...node.question_list)
}
// 题组下还有组
if (node.sub_group_list && node.sub_group_list.length) {
// 将候选顶点入栈，进行下一次循环
stack.push(...node.sub_group_list)
}
}
return res
}
Суммировать
В этой статье процесс глубокого обхода анализируется с помощью графов, а некоторые варианты применяются на практике со ссылкой на его идеи. Лично я считаю идею использования стека для управления древовидным обходом данных очень хорошей.По сравнению с рекурсивной реализацией сложность кода и объемная сложность ниже и проще для понимания.Самое главное, что рекурсия будет занимать память каждый раз, когда он падает.Как только уровень данных станет глубоким, это вызовет ошибку переполнения стека. В будущих бизнес-сценариях, если вы столкнетесь с обходом древовидной структуры, вы можете попробовать эту идею.