Я действительно пытался выявить основные требования в комментариях. К сожалению, мы не могли нормально общаться. Либо ОП не понял, о чем я спрашивал, либо я не мог следить за ответами ОП.
Таким образом, существует ряд различных ответов, которые могут удовлетворить потребности, и это Мне не ясно, какой из них - если таковой имеется - является самым близким.
Но сначала давайте поговорим о структурах данных.
Деревья
Деревья являются одним из Наиболее распространенные структуры данных. Данные в этой проблеме - дерево. Деревья могут быть закодированы разными способами, но основная идея c состоит в том, что существует один узел root, и у него есть некоторое количество потомков. Каждый из этих потомков, в свою очередь, может иметь своих потомков и т. Д.
Это представление дерева, возможно, материнского генеалогического дерева с Betty в root:
Betty
_____|_____
/ \
Kathy Grace
___|___ |
/ | \ |
Alice Carrie Helen Faith
__|__ __|__
/ \ / \
Denise Julie Irene Ellie
|
|
Louisa
У Бетти есть две дочери, Kathy и Grace. У Кэти три дочери; У Грейс есть один, et c.
Если нам нужно что-то сделать с узлами дерева, есть несколько способов, которыми мы могли бы продолжить. Если нам нужно сохранить древовидную структуру, но трансформировать узлы, мы можем map над деревом, возможно, с помощью функции, которая принимает первую букву имени, превращая вышеприведенное в следующее:
B
_____|_____
/ \
K G
___|___ |
/ | \ |
A C H F
__|__ __|__
/ \ / \
D J I E
|
|
L
Если нам не нужно поддерживать форму дерева, а нужно просто посетить каждый узел, тогда мы можем действовать двумя способами. Мы можем go в ширину или в глубину . Ширина в ширину эквивалентна сканированию построчно, так что мы бы посетили это дерево в следующем порядке: Betty, Kathy, Grace, Alice, Carrie, Helen, * 1035. *, Denise, Julie, Irene, Ellie и Louisa.
Depth-first имеет несколько вариантов, предварительный заказ и post -порядок . (Для бинарных деревьев существует другой вариант, называемый по порядку , но он здесь не актуален.) В любом из них мы тщательно исследуем одну ветвь дерева, прежде чем перейти к другой. В предзаказе мы посещаем узел перед посещением его дочерних элементов, что дает нам порядок обхода для этого дерева Betty, Kathy, Alice, Carrie, Denise, Julie, Helen, Grace, Faith, Irene, Louisa и Ellie. В последующем порядке мы посещаем детей, прежде чем посетим узел, что дает порядок обхода Alice, Denise, Julie, Carrie, Helen, Louisa, Irene, Ellie, Faith, Grace и Betty.
(Все эти типы обхода также имеют обратную версию, которую я редко использую и не буду здесь упоминать.)
Ваше дерево покемонов
Данные, которые вы получаете от своего сервисного вызова, образуют дерево со свойством evolves_to, указывающим на дочерние элементы вашего узла. Вопрос в том, чтобы обойти узлы этого дерева. Мне не совсем ясно, какова цель этого обхода, нужно ли вам модифицировать узлы дерева на месте, просто получить определенный контент от каждого в каком-то определенном порядке или в любом порядке, чтобы посещать узлы в данном исправлен порядок построения новой структуры или чего-то еще. Здесь мы обсуждаем варианты, которые делают некоторые из этих вещей.
Во всех них мы передаем функцию для описания наших отношений родитель-ребенок. Идея заключается в том, что основы обхода остаются одинаковыми для многих различных структур. Если у нас есть узел и функция, которая позволяет нам перечислять его дочерние элементы, то мы можем повторно использовать наши обходы через эту и многие другие структуры. Я считаю, что стоит сохранить их, даже если вы не собираетесь повторно использовать код в другом месте сейчас. Это облегчает абстрактное размышление о проблеме и оставляет подробности в другом месте. Таким образом, каждая обсуждаемая основная функция принимает параметр getChildren, который должен быть функцией от узла к массиву дочерних элементов. Во всех этих примерах мы просто передаем его node => node.evolves_to. Но в другой структуре это может быть node => node.children или что-то более сложное.
Сначала в глубину, обход предварительного заказа
Один из способов прохождения узлов и сопоставления их с более полезными для нас узлами состоит в их повторении в глубину. Эта версия выбирает предварительный порядок, в котором родительский узел повторяется перед его дочерними элементами, но изменение его на последующий порядок тривиально.
const depthFirst = (getChildren) => (node) =>
[
node,
... (getChildren (node) || []) .flatMap (depthFirst (getChildren)),
]
const makePokeList = (pokes) =>
depthFirst (node => node.evolves_to) (pokes .chain)
.map (({species}) => species)
const pokes = {baby_trigger_item: null, chain: {evolution_details: [], evolves_to: [{evolves_to: [{evolves_to: [], is_baby: false, species: {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"}}, {evolves_to: [], is_baby: false, species: {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}}], is_baby: false, species: {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"}}], is_baby: false, species: {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"}}, id: 26};
console .log (
makePokeList (pokes)
)
.as-console-wrapper {min-height: 100% !important; top: 0}
depthFirst преобразует наше дерево в массив в предварительном порядке, в глубину. Это generi c, и его можно адаптировать ко многим различным древовидным структурам, передав соответствующую функцию getChildren. (Если вам нужен пост-порядок, то он тривиален: просто поменяйте местами две строки в возвращаемом массиве, возвращая строку node после строки ... getChildren ( ... ).) Обратите внимание, что все, что делает эта функция, это выравнивает это дерево в списке. в правильном порядке.
makePokeList более конкретно c для этой проблемы. Он преобразует дерево с помощью нашей общей функции node => node.evolvesTo в список, удаляя дочерние узлы из каждого элемента, а затем извлекая узел species из наших элементов. Он также начинается с извлечения узла дерева (poke .chan) из большей входной структуры. Это дает нам вывод, подобный следующему:
[
{name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"},
{name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"},
{name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"},
{name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}
]
Функцию depthFirst можно использовать другими способами. Если вы не хотите map просматривать результаты, вы также можете отфильтровать их, уменьшить их до одного значения или даже просто посетить каждый с шаблоном посетителей:
const depthFirst = (getChildren) => (tree) =>
[
tree,
... (getChildren (tree) || []) .flatMap (depthFirst (getChildren)),
]
const visitPokes = (visitor) => (pokes) =>
depthFirst (node => node.evolves_to) (pokes .chain)
.forEach (({evolves_to, ...rest}) => visitor (rest))
const pokes = {baby_trigger_item: null, chain: {evolution_details: [], evolves_to: [{evolves_to: [{evolves_to: [], is_baby: false, species: {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"}}, {evolves_to: [], is_baby: false, species: {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}}], is_baby: false, species: {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"}}], is_baby: false, species: {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"}}, id: 26};
visitPokes (console .log) (pokes)
visitPokes принимает функцию, которая принимает узел и что-то с ним делает. Он ничего не делает с этими результатами, так что в основном это хорошо для генерации побочных эффектов (таких как console.log ging узла или сохранение его в DOM.) Здесь мы проверяем это, просто регистрируя каждый узел.
Обход в ширину
С другой стороны, мы могли бы обойти это в ширину. Это, напомним, посещает всех потомков на одном уровне, прежде чем перейти на следующий. Таким образом, он посещает root, затем всех root детей, затем всех их детей и так далее. Эта версия ломается так же, как и предыдущая:
const breadthFirst = (getChildren) => (nodes) => {
const children = nodes .flatMap (node => getChildren (node) || [])
return [
... nodes,
... (children.length ? breadthFirst (getChildren) (children) : [])
]
}
const makePokesList = (pokes) =>
breadthFirst (node => node .evolves_to) ([pokes .chain])
.map ((({species}) => species) )
const pokes = {baby_trigger_item: null, chain: {evolution_details: [], evolves_to: [{evolves_to: [{evolves_to: [], is_baby: false, species: {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"}}, {evolves_to: [], is_baby: false, species: {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}}], is_baby: false, species: {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"}}], is_baby: false, species: {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"}}, id: 26};
console .log (
makePokesList (pokes)
)
Вы заметите, что результаты выглядят так же, как и на глубине выше. Это только потому, что ваше дерево так просто. Для чего-то более сложного они, вероятно, будут другими.
Функция breadthFirst рекурсивно принимает массив узлов. Но для начала у нас есть один root узел. Здесь мы имеем дело с этим, заключая узел root в массив перед вызовом внутри makePokeList. Часто было бы лучше сделать эту внутреннюю вспомогательную функцию и написать функцию-обертку, которая не делает ничего, кроме выполнения переноса массива, что-то вроде этого:
const _breadthFirst = (getChildren) => (nodes) => {
const children = nodes .flatMap (node => getChildren (node) || [])
return [
... nodes,
... (children.length ? _breadthFirst (getChildren) (children) : [])
]
}
const breadthFirst = (getChildren) => (node) => _breadthFirst (getChildren) ([node])
Тогда, конечно, makePokesList вызовет он использует (poke .chain), а не ([poke .chain]).
Но это в основном незначительный момент. В целом это выглядит очень похоже на наше первое решение для глубины, меняя только порядок итераций. Следующий, однако, существенно отличается:
Map ping наше дерево
Я не могу сказать, что это действительно соответствует вашим требованиям, но другое преобразование не включает итерацию узлов , только отображение текущих узлов в новые, сохраняя древовидную структуру нетронутой. Это было продемонстрировано на первоначальном примере дерева, когда мы создали новое дерево из старого, взяв первую букву каждого узла.
(Это преобразование структуры в другую такой же формы, но с другой данные захватываются классом типов Functor . Об этом очень стоит узнать, но здесь мы далеко уйдем.)
Вот одна из реализаций, снова использующая функцию getChildren, и:
const mapTree = (getChildren, setChildren) => (fn) => (node) =>
setChildren ((getChildren (node) || []) .map (mapTree (getChildren, setChildren) (fn)), fn (node))
const makePokeList = pokes => mapTree
(node => node .evolves_to, (children, node) => ({...node, evolves_to: children}))
(node => node .species)
(pokes.chain)
const pokes = {baby_trigger_item: null, chain: {evolution_details: [], evolves_to: [{evolves_to: [{evolves_to: [], is_baby: false, species: {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"}}, {evolves_to: [], is_baby: false, species: {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}}], is_baby: false, species: {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"}}], is_baby: false, species: {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"}}, id: 26};
console .log (
makePokeList (pokes)
)
Первый параметр mapTree является нашим общим getChildren. Второй - это функция, которая преобразует узел. Он принимает узел и список его дочерних элементов и может возвращать все, что вы хотите, но, вероятно, это новый узел с правильно включенными дочерними элементами. Вероятно, есть несколько более надежная версия, которая включает в себя функцию placeChildren, аналогичную нашей getChildren, которая оставляет основную функцию
. Это приводит к выводу, подобному следующему:
{
"name": "poliwag",
"url": "https://pokeapi.co/api/v2/pokemon-species/60/",
"evolves_to": [
{
"name": "poliwhirl",
"url": "https://pokeapi.co/api/v2/pokemon-species/61/",
"evolves_to": [
{
"name": "poliwrath",
"url": "https://pokeapi.co/api/v2/pokemon-species/62/",
"evolves_to": []
},
{
"name": "politoed",
"url": "https://pokeapi.co/api/v2/pokemon-species/186/",
"evolves_to": []
}
]
}
]
}
Если вам не нужны пустые children узлы, вы можете заменить (children, node) => ({...node, evolves_to: children}) на (children, node) => ({...node, ...(children.length ? {evolves_to: children} : {})}). Или, если вам нужно другое имя для дочерних узлов, вы можете написать (children, node) => ({...node, kids: children}) или просто (children, node) => ({...node, children}).
Это, конечно, не дает вам никакого конкретного порядка итерации; это просто создает новое дерево. Но это может быть то, что вам нужно.
Вложенный массив на основе уровней
Самое близкое, что я могу найти к тому, на что вы похожи, - метод, который группирует вещи по уровням. В нашем исходном дереве это означало бы вложенный массив, такой как
[
['Betty'],
['Kathy', 'Grace'],
['Alice', 'Carrie', 'Helen', 'Faith'],
['Denise', 'Julie', 'Irene', 'Ellie'],
['Louisa']
]
. Лично я считаю, что это довольно странная структура. Например, он не позволит вам различить guish между этими двумя деревьями:
B B
_____|_____ _____|_____
/ \ / \
K G K G
___|___ | ___|___ __|__
/ | \ | / \ / \
A C H F A C H F
__|__ __|__ | | | |
/ \ / \ | | | |
D J I E D J I E
| |
| |
L L
Но если это то, что вы хотите, мы можем создать что-то подобное из расширения нашей глубины. Первый поиск. Хитрость заключается в том, чтобы захватить некоторую дополнительную информацию для наших узлов. Если мы отслеживаем происхождение нашего узла из root, а также его содержимое, то это легко построить, сгруппировав по длине массива предков. Это также позволило бы нам делать более сложные вещи, такие как создание узлов, таких как poliwag > poliwhirl > poliwrath и poliwag > poliwhirl > politoed из вашего ввода, что может быть полезно.
Так что в этой версии depthFirst содержит дополнительный параметр вокруг узла, называемого path:
const depthFirst = (getChildren) => (tree, path) =>
[
{node: tree, path},
... (getChildren (tree) || []) .flatMap (node => depthFirst (getChildren) (node, [... path, tree]))
]
const makePokes = pokes =>
Object .values (depthFirst (node => node .evolves_to) (pokes .chain, [])
.map (({node, path}) => ({node, depth: path .length}))
.reduce ((a, {node, depth}) => ({...a, [depth]: [...(a [depth] || []), node .species]}), {}))
const pokes = {baby_trigger_item: null, chain: {evolution_details: [], evolves_to: [{evolves_to: [{evolves_to: [], is_baby: false, species: {name: "poliwrath", url: "https://pokeapi.co/api/v2/pokemon-species/62/"}}, {evolves_to: [], is_baby: false, species: {name: "politoed", url: "https://pokeapi.co/api/v2/pokemon-species/186/"}}], is_baby: false, species: {name: "poliwhirl", url: "https://pokeapi.co/api/v2/pokemon-species/61/"}}], is_baby: false, species: {name: "poliwag", url: "https://pokeapi.co/api/v2/pokemon-species/60/"}}, id: 26};
console .log (
makePokes (pokes)
)
Это избыточное решение для нашей текущей проблемы, и мы могли бы просто пропустить параметр depth. Но функции, подобные этой, должны быть довольно общими c, и, поскольку у нас есть весь путь, кажется, что лучше предоставить его, позволяя нашему коду проблемы, makePokes, иметь дело только с использованием соответствующего бита, length массива paths.
makePokes здесь более сложный. Мы используем эту версию depthFirst для сбора массива {node, path} объектов, а затем группируем свойства species узлов в массивы в соответствии с длиной пути, затем вызываем Object.values, чтобы взять только эти массивы .
Выводы
Нет, неважно, я слишком устал. Я надеюсь, что один из этих методов работает для вас.