Обход структурированных данных древовидного типа с использованием JavaScript
У меня есть набор данных, в котором есть родительские и вложенные дочерние элементы. Целью этих данных является переход от родителя к -> child1 к -> Child1Child..... -> дочерний2 до -> дочерний1 до -> дочерний2 до -> дочерний3 -> ребенок3 -> ребенок4
Как только конец узла будет достигнут, начните движение в обратном направлении от конца узла к началу, например. child2, где другие дети были остановлены и еще не посещались.
Набор данных в отношениях родитель-потомок
[
{
"id": 0,
"children": [
{
"id": 3,
"parentId": 0,
"children": [
{
"id": 6,
"parentId": 3,
"children": [
{
"id": 11,
"parentId": 6,
"children": [
{
"id": 10,
"parentId": 11,
"children": [
{
"id": 8,
"parentId": 10,
}
]
}
]
},
{
"id": 9,
"parentId": 6,
"children": [
{
"id": 1,
"parentId": 9,
"children": [
{
"id": 7,
"parentId": 1,
}
]
}
]
},
{
"id": 4,
"parentId": 6,
}
]
}
]
}
]
}
]
let result = [];
const handleTree = ( tree, count) => {
count = count || 0
const tree = _.clone(data);
if ( tree ){
tree.forEach( ( t: any, i: string | number ) => {
let deepCopy = _.clone({...t });
delete deepCopy.children;
const { id, parentId } = deepCopy
result.push({ id, isVisited: true, parentId });
if ( tree[i].children ){
handleTree(tree[i].children, count+1 )
}else{
//Completed start reading backward
// const getPreviousParent = findParentDetails(tree[i].parentId )
}
})
}
}
Как подойти к этой проблеме? До сих пор мне удавалось читать данные в том же направлении, но при движении назад я получал неожиданные результаты.
Надеюсь, я хорошо объяснил вопрос и он имеет смысл. Предложения приветствуются.
![Безумие обратных вызовов в javascript [JS]](https://i.imgur.com/WsjO6zJb.png)
Ответы 2
Это очень похоже на поиск в глубину (DFS) с древовидной структурой.
Я думаю, что в отношении направления вперед ваш подход правильный. Для обратного направления вам необходимо поддерживать стек узлов. Если вы достигнете узла без дочерних узлов, вам нужно извлечь его из стека и посетить другие оставшиеся дочерние узлы.
Вы можете сделать что-то вроде этого:
let result = [];
let stack = [];
const handleTree = (tree, count) => {
count = count || 0;
if (tree) {
tree.forEach((t, i) => {
let deepCopy = {...t};
delete deepCopy.children;
const { id, parentId } = deepCopy;
result.push({ id, isVisited: true, parentId });
if (t.children) {
// push current node to stack
stack.push({node: t, index: i+1});
// recursively call handleTree for children
handleTree(t.children, count+1);
} else {
// if no children, start backtracking
while (stack.length > 0) {
let top = stack[stack.length - 1]; // peek top of stack
if (top.node.children && top.index < top.node.children.length) {
// if top node has unvisited children, visit them
handleTree([top.node.children[top.index]], count+1);
top.index++; // increment index of top node
} else {
// if no unvisited children, pop from stack
stack.pop();
}
}
}
});
}
};
Некоторые комментарии к вашей попытке:
- Нет необходимости что-либо клонировать при деструктуризации на примитивы. Кроме того, удаление
childrenиз клона не потребуется. - Чтобы предметы также добавлялись на обратном пути, просто сделайте то же самое (то же самое
result.push), что и на пути вниз. - Вам не нужен
i. Ваша переменная цикла — это нужный вам объект узла. - В вашем коде нет смысла использовать
count. Но я добавил его в сгенерированные элементы. Лучше, чтобы счетчик был одним числом, чем отдельной переменной для каждого выполнения, чтобы избежать дублирования. Для этого вы можете обернуть этот единственный счетчик в объект. - Если каждый выходной объект получает свойство
visited: true, то он не добавляет никакой полезной информации.
Для такого обхода пригодится генератор: таким образом вы не требуете, чтобы результаты собирались в массиве - вы оставляете на усмотрение вызывающей стороны решать, что делать со значениями и следует ли прерывать обход. .
Вы также можете добавить свойство, указывающее направление (вниз или вверх).
Вот возможная реализация:
// Define a generator
function* handleTree(tree, counter = {node: 0}) {
for (const node of tree ?? []) {
// No need to clone when you destructure into primitive values:
const {id, parentId, children} = node;
const current = { id, parentId, direction: "down", ...counter };
counter.node++;
yield current;
if (children) {
yield* handleTree(children, counter);
}
yield {...current, direction: "up" }; // change the direction
}
}
// Your example tree:
const tree = [{"id": 0,"children": [{"id": 3,"parentId": 0,"children": [{"id": 6,"parentId": 3,"children": [{"id": 11,"parentId": 6,"children": [{"id": 10,"parentId": 11,"children": [{"id": 8,"parentId": 10,}]}]},{"id": 9,"parentId": 6,"children": [{"id": 1,"parentId": 9,"children": [{"id": 7,"parentId": 1,}]}]},{"id": 4,"parentId": 6,}]}]}]}];
const result = [...handleTree(tree)]; // Collect into array
console.info(result);как я могу добавить сюда добавочный идентификатор, который должен увеличиваться при уменьшении. Оно не должно увеличиваться при движении вверх.
Каким должен быть идентификатор элементов, обозначающих движение вверх?
Идентификатор не в заказе. Я хочу вести здесь учет детей, например. Узел 1, Узел 2, Узел 3 и т. д.
Вы имеете в виду, что это детский номер? Итак, если у ребенка есть ребенок, должен ли этот ребенок снова получить номер 1? Если нет, то как должна выглядеть нумерация?
Нет, Дочерний элемент 1 -> Узел 1 Дочерний элемент Дочернего элемента 1 -> Узел 2........... Дочерний элемент n -> Узел 3
И должно ли это регистрироваться в возвращаемом элементе? А как насчет восходящих элементов, какой номер они тогда должны получить?
Правильно, это должно быть зарегистрировано для ребенка во время спуска. Для восходящих элементов это не должно регистрироваться, потому что мы уже добавляем этот инкрементальный счетчик/идентификатор при движении вниз. То же самое должно быть и для нисходящих элементов.
Извините, я не понимаю. Элементы, расположенные вверх, являются отдельными объектами. Какой номер для них?
Давайте продолжим обсуждение в чате.
Обновил ответ согласно вашим объяснениям.
возможно, вы можете использовать алгоритм поиска в глубину (DFS) для обхода этой древовидной структуры данных, IIRC использует стек и хэш-набор для хранения посещенных и непосещенных узлов для каждой вершины. Я использовал его однажды для решения аналогичной проблемы. Вот Руководство по JS о том, как это сделать. Надеюсь это поможет.