从嵌套对象树获取路径

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"逻辑更具可读性; 遗憾的是,你不能像{ x.a, x.b } = obj在结构化赋值中那样使用复合结构,所以slice函数就像你将要获得的一样好(你可以说{a,b} = obj但是你不能添加额外的嵌套级别来获得一个对象切片).