Иерархический JSON - найти полный путь к объекту
У меня есть большой объект JSON, который служит для источника дерева. в этом JSON мне нужно найти объект с заданным идентификатором и создать для него завершение, что означает сбор его родителей. Для иллюстрации это как в файловой системе: folde1/folder2/folder3/file.txt. Вот моя рекурсивная функция для поиска объекта:
private find(source, id): string[] {
for (const key in source)
{
var item = source[key];
if (item.id === id) {
return this.indexes;
}
if (item.children) {
this.indexes.push(key);
var subresult = this.find(item.children, id);
if (subresult) {
this.indexes.push(key);
return this.indexes;
}
}
}
return null;
}
Моя проблема в том, что при поиске объекта я нахожу много ложных родителей, поэтому результат имеет дополнительные данные.
Любая идея, как заставить это работать? Тоже думаю начать искать путь изнутри, но не знаю как получить родителя найденного объекта.
Спасибо за помощь.
О, мальчик, спасибо! Проблема со вторым языком :(
Ответы 1
Я собираюсь дать общий ответ, и, надеюсь, он применим к вашей фактической структуре. Я предполагаю, что Tree выглядит так:
interface Tree {
id: string;
children?: Record<string, Tree>;
}
Каждый Tree имеет id и необязательное свойство children, которое представляет собой словарь Trees. Возможная реализация findPathById() выглядит следующим образом:
function findPathById(tree: Tree, id: string, curPath: string[] = []): string[] | undefined {
if (tree.id === id) return curPath;
const children = tree.children ?? {}
for (let k in children) {
const possibleAnswer = findPathById(children[k], id, [...curPath, k]);
if (possibleAnswer) return possibleAnswer;
}
return undefined;
}
Подход здесь заключается в том, что функция принимает параметр curPath, соответствующий пути к текущему узлу дерева, к которому могут быть добавлены последующие записи пути. Если этот путь не указан, то он будет считаться пустым. Если переданный tree содержит искомый id, то мы его нашли и можем вернуть curPath. В противном случае мы начинаем проверять каждое свойство children (если оно существует), чтобы увидеть, существует ли идентификатор в одном из дочерних элементов, вызывая findPathId для дочернего значения, с новым curPath, созданным путем добавления дочернего ключа к текущему пути. Если мы получаем результат, мы возвращаем его. В противном случае мы переходим к следующему ребенку. Если мы не нашли идентификатор после проверки текущего элемента и рекурсивно вниз по его дочерним элементам, то его там нет, и мы возвращаем undefined.
Вот тест:
const tree: Tree = {
id: "A",
children: {
x: {
id: "B", children: {
t: { id: "E" },
u: { id: "F" }
}
},
y: {
id: "C", children: {
v: { id: "G" },
w: { id: "H" }
}
},
z: { id: "D" }
}
}
console.info(findPathById(tree, "A")); // []
console.info(findPathById(tree, "D")); // ["z"]
console.info(findPathById(tree, "G")); // ["y", "v"]
console.info(findPathById(tree, "J")); // undefined
Это похоже на поведение, которое мы хотим. Идентификатор "A" находится в корне, поэтому путь представляет собой пустой массив. Идентификатор "D" находится в tree.children.z, поэтому путь ["z"]. Идентификатор "G" находится в tree.children.y.children.v, поэтому путь ["y", "v"]. И, наконец, идентификатор "J" никогда не будет найден, поэтому путь будет undefined.
«Иератический» на самом деле слово, поэтому я не собираюсь его менять, но я думаю, что вы имеете в виду «Иерархический» :).