javascript - JS中的递归数组枚举

Question

请告诉我如何遍历具有未知嵌套的数组？情况是这样的，我在初始阶段练习js和reactjs，我用Pokemon开发了一个应用程序，我想派生一个带有Evolution的组件:)。 API返回以下形式的对象：

{
  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
};

嵌套的 evolves_to数组的数量可以很多。在 "evolves_to"内可以有多个对象，即，一种类型的多层开发。事实证明（我认为这样的结构在将来的工作中会很方便）：

[
    [
      {
        name: "",
        url: ""
      }
    ],
    [
      {
        name: "",
        url: ""
      },
      {
        name: "",
        url: ""
      }
    ][
      {
        name: "",
        url: ""
      }
    ]
  ]

也就是说，具有第一级演化的第一阵列，第二级阵列，具有两种类型的阵列的第二级，分别是第三级阵列，第三级等。
如果嵌套是未知的，那么我需要以某种方式进行递归操作吗？我尝试使用 map, reduce ...我试图将递归注入其中...但是很遗憾，我还没有想到。如果没有困难，请帮助。先感谢您 ）

UPD：
这是evolves_to将.species收集到单个对象并添加到数组的代码。但没有考虑到Evolutions_to中是否存在几种物种。如果它们处于同一级别，则它们应位于同一数组中：

data={
  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
};

let resultUPD = [];
resultUPD.push([data.chain.species]);
const getEvolves = object => {
  if (Array.isArray(object.evolves_to) && !object.evolves_to.length) {
    return object.evolves_to;
  }
  const resultNew = object.evolves_to.map(evolves =>
    getEvolves(evolves)
  );
  return [...object.evolves_to, ...resultNew].flat();
};
getEvolves(data.chain).map(elem =>
  resultUPD.push([elem.species])
);
console.log("result", resultUPD);

Answer 1

我确实确实尝试挑出评论中的基本要求。不幸的是，我们似乎无法正确沟通。 OP可能不理解我的要求，或者我听不懂OP的回答。

因此，有许多不同的答案可以满足需求，但我不清楚哪一个（如果有的话）最接近。

但首先，让我们谈谈数据结构。

树木

树是最常见的数据结构之一。此问题中的数据是一棵树。可以用许多不同的方式对树进行编码，但是基本思想是只有一个根节点，并且它具有一定数量的后代。这些子孙中的每个子孙又可以具有自己的子孙，依此类推。

这是一棵树的表示形式，也许是一棵以Betty为根的母系家谱：

                           Betty
                        _____|_____
                       /           \
                    Kathy          Grace
                   ___|___           |
                  /   |   \          |
             Alice  Carrie Helen   Faith
                    __|__          __|__
                   /     \        /     \
                Denise  Julie  Irene   Ellie
                                 |
                                 |
                              Louisa 

贝蒂有两个女儿 Kathy和 Grace。凯西有三个女儿。恩典有一个，等等。

如果我们需要对树的节点做一些事情，可以采取几种方法。如果我们需要保留树的结构，但要转换节点，则可以在树上 map，也许可以使用一个使用名称首字母的函数，将上面的代码变成这样：

                             B
                        _____|_____
                       /           \
                      K             G
                   ___|___          |
                  /   |   \         |
                 A    C    H        F
                    __|__         __|__
                   /     \       /     \
                  D       J     I       E
                                |
                                |
                                L 

如果我们不需要维护树的形状，而只需要访问每个节点，则可以采用两种常用方法。我们可以去 breadth-first或 depth-first。广度优先等效于逐行扫描，因此我们将按 Betty， Kathy， Grace， Alice， Carrie， Helen， ， Faith， Denise， Julie， Irene和 Ellie。

深度优先具有多个变体 pre-order和 post-order。 （对于二叉树，还有另一个变体，称为 in-order，但这在这里无关紧要。）在它们中的任何一个中，我们都先深入探索树的一个分支，然后再移至另一个。在预订时，我们先访问节点，再访问其子节点，这为我们提供了 Louisa， Betty， Kathy， Alice， Carrie， Denise， ， Julie， Helen， Grace， Faith和 Irene。在后序中，我们先访问子节点，然后再访问节点，遍历顺序为 Louisa， Ellie， Alice， Denise， Julie， Carrie， Helen，< cc>， Louisa， Irene和 Ellie。

（所有这些遍历类型都具有相反的版本，我很少使用，在此不再赘述。）

你的口袋妖怪树

从服务调用中获取的数据形成一棵树，其中的 Faith属性指向节点的子级。问题是关于遍历此树的节点。对我来说，这种遍历的目的是什么还不是很清楚，是否需要修改就位的树的节点，以简单的顺序或以任何顺序从每个树中获取某些内容，以访问给定的节点固定顺序以构建新结构或其他内容。在这里，我们讨论了做这些事情的变体。

在所有这些方法中，我们都传递一个函数来描述我们的父子关系。这个想法是遍历的基础对于许多不同的结构保持不变。如果我们有一个节点和一个允许我们列出其子节点的函数，则可以在该结构和许多其他结构上重用遍历。我发现值得保留这些，即使您现在不打算在其他地方重用代码。这样可以更轻松地抽象思考问题，并将细节留在其他地方。因此，讨论的每个主要函数都带有参数 Grace，该参数必须是从节点到子项数组的函数。在所有这些示例中，我们仅将其传递为 Betty。但是在另一种结构中，它可能是 evolves_to或更复杂的东西。

深度优先，预遍历

遍历节点并将它们映射到对我们更有用的节点的一种方法是以深度优先的方式迭代它们。此版本选择进行预订购，在该订购中，父节点在其子节点之前进行迭代，但是将其更改为后订购是微不足道的。

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}

getChildren以深度优先的方式将树转换为数组。这是通用的，可以通过传递适当的 node => node.evolves_to函数来适应许多不同的树结构。 （如果您想要后置订单，这很简单：只需交换返回数组中的两行，在 node => node.children之后返回 depthFirst行。）请注意，此函数所做的所有操作都是将树平整化为列表在
正确的顺序。
getChildren更特定于此问题。它使用我们常见的 node函数将树转换为列表，从每个元素中删除子节点，然后从我们的元素中提取 ... getChildren ( ... )节点。它还从较大的输入结构中抢走树节点（ makePokeList）开始。这将为我们提供如下输出：

[
    {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/"}
]

node => node.evolvesTo函数可以以其他方式使用。如果您不想对结果进行 species过滤，也可以过滤它们，将它们减少为单个值，甚至可以简单地使用访问者模式访问每个结果：

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)

poke .chan接受一个接受节点并对其执行某些操作的函数。它对这些结果不做任何事情，因此，这对于产生副作用（例如 depthFirst结点节点或将其存储在DOM中）最有用。在这里，我们通过简单地记录每个节点来对其进行测试。


广度优先遍历

或者，我们可以以广度优先的方式遍历。回想一下，在访问下一级之前，先拜访了所有后代。因此，它访问根，然后访问根的所有子代，然后访问其所有子代，依此类推。这个版本的崩溃很像早期版本：

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)
)

您会注意到结果看起来像上面的深度优先。那仅仅是因为你的树是如此简单。对于更复杂的事情，这些可能会有所不同。

map函数以递归方式获取节点数组。但是首先，我们只有一个根节点。在这里，我们通过在调用之前在 visitPokes内将根节点包装在数组中来进行处理。通常，最好做一个内部帮助器函数并编写一个包装器函数，该函数只需要进行数组包装即可，就像这样：

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])

然后，当然 console.log会使用 breadthFirst而不是 makePokeList来调用它。

但这主要是一个小问题。总体而言，这与我们的深度优先解决方案非常相似，只更改了迭代顺序。但是，以下内容有很大不同：

makePokesList ping我们的树

我不能说这确实符合您的要求，但是另一种转换不涉及节点的迭代，而只是将当前节点映射到新节点，从而保持树结构完整。当我们通过取每个节点的第一个字母从旧树创建一棵新树时，这在树的最初示例中得到了证明。

（这种将结构转换为相同形状但具有不同数据的结构的转换由类型类 Functor捕获。这非常值得学习，但在这里会带给我们更远的地方。）

这是一个实现，再次使用 (poke .chain)函数，并且：

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)
)

([poke .chain])的第一个参数是我们常见的 Map。第二个是转换节点的功能。它接受一个节点及其子节点列表，并可以返回您想要的任何内容，但是大概它是一个新的节点，其中包含了正确的子节点。可能有一个更健壮的版本，其中包括与我们的 getChildren类似的 mapTree函数，该函数将保留主要功能

这将产生如下输出：

{
  "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": []
        }
      ]
    }
  ]
}

如果您不希望空的 getChildren节点，可以将 placeChildren替换为 getChildren。或者，如果您想为子节点使用不同的名称，则可以编写 children，也可以编写 (children, node) => ({...node, evolves_to: children})。

当然，这不会给您任何特定的迭代顺序。它只是创建一棵新树。但这可能就是您所需要的。

基于级别的嵌套数组

我所能找到的最接近您所要求的是一种按级别对事物进行分组的技术。在我们的初始树中，这意味着像

[
  ['Betty'],
  ['Kathy', 'Grace'],
  ['Alice', 'Carrie', 'Helen', 'Faith'],
  ['Denise', 'Julie', 'Irene', 'Ellie'],
  ['Louisa'] 
]

我个人认为这是一个相当奇怪的结构。例如，它不会让您区分这两个树：

                 B                               B            
            _____|_____                     _____|_____       
           /           \                   /           \      
          K             G                 K             G     
       ___|___          |              ___|___        __|__     
      /   |   \         |             /       \      /     \
     A    C    H        F            A         C    H       F     
        __|__         __|__          |         |    |       |
       /     \       /     \         |         |    |       |  
      D       J     I       E        D         J    I       E 
                    |                |                
                    |                |                      
                    L                L 

但是，如果您要使用它，我们可以在深度优先搜索的扩展中创建类似的内容。诀窍是将一些其他信息捕获到我们的节点。如果我们从根开始跟踪节点的祖先及其内容，则可以通过对祖先数组的长度进行分组来轻松构建它。这也可以让我们做更复杂的事情，例如建立 (children, node) => ({...node, ...(children.length ? {evolves_to: children} : {})})和
(children, node) => ({...node, kids: children})超出您的输入范围，这可能会很有用。

因此，在此版本中， (children, node) => ({...node, children})在节点旁边带有一个额外的参数，称为 poliwag > poliwhirl > poliwrath：

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)
)

这对于我们当前的问题来说是过大了，我们可以绕过 poliwag > poliwhirl > politoed参数。但是这样的函数是相当通用的，并且由于我们具有完整的路径，因此提供它似乎更好，让我们的问题特定代码 depthFirst仅使用相关位，即 path depth数组。

makePokes在这里更复杂。我们使用此版本的 length收集 paths对象的数组，然后根据路径的长度将节点的 makePokes属性分组为数组，然后调用 depthFirst仅获取这些数组。

结论

不，没关系，我太累了。我希望其中一种技术对您有用。