javascript - 从嵌套对象树获取路径

Question

我目前遇到了一个问题，当我开始时似乎不难解决，但我现在被困了几个小时，所以我们开始:

给定这个对象数组:

groups = [
  {
    name: 'Custard apple',
    slug: 'custard-apple',
    children: [
      {
        name: 'Vanilla',
        slug: 'vanilla',
        children: [
          {
            name: 'Strawberry',
            slug: 'strawberry',
            children: []
          }, {
            name: 'Pineapple',
            slug: 'pineapple',
            children: []
          }
        ]
      }, {
        name: 'Chocolate',
        slug: 'chocolate',
        children: []
      }
    ]
  }, {
    name: 'Raspberry',
    slug: 'raspberry',
    children: []
  }, {
    name: 'Lemon',
    slug: 'lemon',
    children: [
      {
        name: 'Orange',
        slug: 'orange',
        children: [
          {
            name: 'Coconut',
            slug: 'coconut',
            children: []
          }
        ]
      }, {
        name: 'Almond',
        slug: 'almond',
        children: []
      }
    ]
  }
];

我正在尝试找到一个函数，在给定 slug 的帮助下为我提供对象的路径:

var find_path = function(groups, slug) { /* looking for a solution to this */ };
result = find_path(groups, 'pineapple'); 

console.log(result);
// [{ name: 'Custard Apple', slug: 'custard-apple' }, { name: 'Vanilla', slug: 'vanilla'}, { name: 'Pineapple', slug: 'pinapple' }]

// another example
result = find_path(groups, 'lemon');
console.log(result);
// [{ name: 'Lemon', slug: 'lemon' }]

我尝试了几种递归方法，尝试保存函数调用的路径，但通常会得到重复的结果/通常不是所需的结果。我主要围绕递归查找结合(失败的)尝试保存沿途路径。

那么，有没有一种递归的方法来解决这个问题呢？还是我想得太复杂了？

Answer 1

您正在处理一棵树，因此递归是一个自然的解决方案。简单的深度优先搜索(查看当前节点，然后查看其子节点)可能是最简单的解决方案。像这样的事情:

slice = (o, properties...) ->
    ret = { }
    ret[p] = o[p] for p in properties
    ret

find_path = (a, slug) ->
    for o in a
        # Bail out now if this is what we're looking for.
        if(o.slug == slug)
            return [ slice(o, 'name', 'slug') ]
        # Scan the children if not.
        if(sub = find_path(o.children, slug))
            return [ slice(o, 'name', 'slug') ].concat(sub)
    # Explicitly return `undefined` to make sure the caller
    # gets The Right Thing back.
    return

演示:http://jsfiddle.net/ambiguous/3FNZy/

递归中的每一步都不会为您提供任何内容，也不会提供从当前节点到您要查找的节点的路径。然后展开递归，构建通过 concat 的路径来电。当然，这里进行了相当多的数组复制，但是对于像这样的小数据集来说，不值得担心(如果您有更多数据，那么您会想要切换到某种索引结构)。

slice 函数只是为了使“复制 e 但不复制 e.children”逻辑更具可读性；不幸的是，您不能在 destructured assignment 中使用像 { x.a, x.b } = obj 这样的复合结构因此 slice 函数与您想要的一样好(您可以说 {a,b} = obj 但您可以不要添加额外的嵌套级别来获取对象切片)。