如何将树状数组和对象的嵌套数据结构转换为具有 computed/counted id 和跟踪父 id 的项目列表？

Question

一个API returns 数组和对象的嵌套数据结构。数据以树状对象列表的形式出现，每个对象都有可能的父子关系。结构本身由以下示例代码显示。

[{
  label: "search me",
  value: "searchme",
  children: [{

    label: "search me too",
    value: "searchmetoo",
    children: [{

      label: "No one can get me",
      value: "anonymous",
    }],
  }],
}, {
  label: "search me2",
  value: "searchme2",
  children: [{

    label: "search me too2",
    value: "searchmetoo2",
    children: [{

      label: "No one can get me2",
      value: "anonymous2",
    }],
  }],
}]

必须将上述数据转换为一个（平面）对象数组，其中每个对象将代表一个前节点元素，但具有唯一的主键 (id)。此外，除了没有父节点的根节点外，节点的父 ID 等于其父节点的 ID（主键），因此父 ID 应为空。

上面提供的源数据的目标结构然后匹配下面的代码...

[{
  id: 1,                // DIAGID
  parentId: null,       // PARENTID
  label: "search me",   // DIAGNOSIS
  value: "searchme"     // DIAGTYPE
}, {
  id: 2,
  parentId: 1,
  label: "search me too",
  value: "searchmetoo"
}, {
  id: 3,
  parentId: 2,
  label: "No one can get me",
  value: "anonymous"
}, {
  id: 4,
  parentId: null,
  label: "search me2",
  value: "searchme2"
}, {
  id: 5,
  parentId: 4,
  label: "search me too2",
  value: "searchmetoo2"
}, {
  id: 6,
  parentId: 5,
  label: "No one can get me2",
  value: "anonymous2"
}]

Answer 1

您可以对 Array#flatMap 采取递归方法并存储 parent 以供下一次调用。

此方法为所有节点递增 id。

const
    flatTree = (id => parent => ({ children = [], ...object }) => [
        { id: ++id, ...object, parent },
        ...children.flatMap(flatTree(id))
    ])(0),
    tree = [{ label: 'search me', value: 'searchme', children: [{ label: 'search me too', value: 'searchmetoo', children: [{ label: 'No one can get me', value: 'anonymous' }] }] }, { label: 'four', searchme: '4four' }],
    flat = tree.flatMap(flatTree(null));

console.log(flat);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

这是一个递归函数dfs，它通过输入树执行预序遍历，并传递一个计数器，该计数器提供 id 属性将在输出。此外，当前节点的 id 作为 parentId 传递给递归调用：

const dfs = (children, counter={id: 1}, parentId=null) =>
    children.flatMap(({children=[], ...node}) => [{ 
        ...counter, 
        parentId,
        ...node
    }].concat(dfs(children, counter, counter.id++)));

const response = [{label: "search me",value: "searchme",children: [{label: "search me too",value: "searchmetoo",children: [{label: "No one can get me",value: "anonymous",}],}],}, {label: "search me2",value: "searchme2",children: [{label: "search me too2",value: "searchmetoo2",children: [{label: "No one can get me2",value: "anonymous2",}],}],}];
const result = dfs(response);
console.log(result);

Answer 3

我本来想说递归树遍历就是您所需要的，但您可以使用生成器轻松完成同样的事情：

function *visitNodes( root, parent = null, id = 0 ) {
  
  const node = {
    ...root,
    id : ++id,
    parentId = parent ? parent.id : null
  };
  delete node.children;
  
  yield node;
  
  for ( const child of root.children ?? [] ) {
    yield *visitNodes(child, node, id);
  }
  
}

定义生成器后，您可以迭代节点：

for (const node of visitNodes( tree ) ) {
  // do something useful with node here
}

您可以轻松地将其转换为列表，或者使用扩展运算符：

const nodes  = [...visitNodes(tree)];

或使用 Array.from():

const nodes = Array.from( visitNodes(tree) );

Answer 4

单个递归实现的 reduceer 功能通常可以映射和收集任何项目。

它使用一个 collector 对象作为 reduce method's 2nd argument（和 reducer 的初始值）。 collector 的 result 数组收集任何项目。并且 count 不断增加并分配为收集项目的 id（以前的 DIAGID），而项目的 parentId（以前的 PARENTID）会根据需要按顺序更新始终反映当前的递归调用堆栈...

function countMapAndCollectNestedItemRecursively(collector, item) {

  let { count = 0, parentId = null, result } = collector;
  const { children = [], ...itemRest } = item;

  result.push({

    id: ++count,
    parentId,

    ...itemRest,
  });
  count = children.reduce(

    countMapAndCollectNestedItemRecursively,
    { count, parentId: count, result }

  ).count;

  return { count, parentId, result };
}

const sampleData = [{
  label: "FOO",
  value: "foo",
  children: [{

    label: "FOO BAR",
    value: "fooBar",
    children: [{

      label: "FOO BAR BAZ",
      value: "fooBarBaz",
    }],
  }, {
    label: "FOO BIZ",
    value: "fooBiz",
    children: [{

      label: "FOO BIZ BUZ",
      value: "fooBizBuz",
    }],
  }],
}, {
  label: "BAR",
  value: "bar",
  children: [{

    label: "BAR BAZ",
    value: "barBaz",
    children: [{

      label: "BAR BAZ BIZ",
      value: "barBazBiz",
      children: [{

        label: "BAR BAZ BIZ BUZ",
        value: "barBazBizBuz",
      }],
    }, {
      label: "BAR BAZ BUZ",
      value: "barBazBuz",
    }],
  }, {
    label: "BAR BIZ",
    value: "barBiz",
    children: [{

      label: "BAR BIZ BUZ",
      value: "barBizBuz",
    }],
  }],
}];

console.log(
  sampleData.reduce(

    countMapAndCollectNestedItemRecursively,
    { result: [] },

  ).result
);

.as-console-wrapper { min-height: 100%!important; top: 0; }

Answer 5

这个版本融合了 trincot 和 Nicholas Carey 的想法。从 trincot 的回答（实际上回答了一个不同但密切相关的问题）我窃取了他的 {ctr: id: 1} 处理。从 Nicholas 那里，我使用生成器更容易地迭代值，尽管我从那里简化了一点。

我认为它们结合起来可以提供一个很好的解决方案：

const flatten = function * (xs, ctr = {id: 1}, parent = null) {
  for (let {children = [], ...x} of xs) {
    const node = {id: ctr .id ++, parentId: parent ? parent .id : null, ...x}
    yield node
    yield * flatten (children, ctr, node)
  }
}

const transform = (xs) => [...flatten (xs)]

const response = [{label: "search me", value: "searchme", children: [{label: "search me too", value: "searchmetoo", children: [{label: "No one can get me", value: "anonymous"}]}]}, {label: "search me2", value: "searchme2", children: [{label: "search me too2", value: "searchmetoo2", children: [{label: "No one can get me2", value: "anonymous2"}]}]}]

console .log (transform (response))

.as-console-wrapper {max-height: 100% !important; top: 0}

如何将树状数组和对象的嵌套数据结构转换为具有 computed/counted id 和跟踪父 id 的项目列表？

How does one convert a tree like nested data structure of arrays and objects into a list of items with computed/counted id's and tracked parent id's?

javascript

arrays

recursion

data-structures

mapping