我有一个这样的JavaScript数组：

let myArray = [
   { name: 'Alice', children: ['Bob', 'Bill'] },
   { name: 'Bob', children: 'Cindy' },
   { name: 'Bill', children: [] },
   { name: 'Cindy', children: ['David', 'Don'] },
   { name: 'David' },
   { name: 'Don' },
]

我想从中获取分层数据，也就是说，我想把数组展示成如下形式：

Alice
  Bob
    Cindy
      David
      Don
  Bill

或者

Alice
Alice -> Bob
Alice -> Bob -> Cindy
Alice -> Bob -> Cindy -> David
Alice -> Bob -> Cindy -> Don
Alice -> Bill

很多关系型数据库提供此类功能，例如Oracle的 [CONNECT BY] 子句，或者MongoDB的 [$graphLookup] 聚合操作符

我可以把这个数组插入到Oracle表或MongoDB集合中，然后运行上述查询之一，但我正在寻找一个不使用数据库的解决方案。

解决方案

与此同时找到了一个与我前面提到的数据库函数非常接近的解决方案。

function connectBy(array, startWith, connectWith, path = [], level = 0) {
   const filterFn = typeof startWith == 'function' ?
      startWith :
      function (x) {
         const children = startWith[startWith.length - 1][connectWith[1]];
         return Array.isArray(children) ? children.includes(x[connectWith[0]]) : children == x[connectWith[0]];
      };
   for (let item of array.filter(filterFn)) {
      if (path.includes(array.indexOf(item)))
         item.isCycle = true;    
      item.level = level;
      item.path = path.concat(array.indexOf(item));
      typeof startWith == 'function' ? startWith = [item] : startWith.push(item);
      if (!item.isCycle)
         startWith = connectBy(array, startWith, connectWith, item.path, level + 1);
   }
   return startWith;
}

参数 startWith 是一个用于获取顶层项的函数。connectWith 是一个由两个字符串组成的数组，用于定义用于连接的字段。

const myArray = [
   { name: 'Alice', children: ['Bob', 'Bill'] },
   { name: 'Bob', children: 'Cindy' },
   { name: 'Bill', children: [] },
   { name: 'Cindy', children: ['David', 'Don'] },
   { name: 'David',children: ['Bob'] },
   { name: 'Don' },
];
const arr = connectBy(
   myArray, 
   function (val) { return val.name == 'Alice'}, 
   ['name', 'children']
);

[
  { name: 'Alice', children: [ 'Bob', 'Bill' ], level: 0, path: [ 0 ] },
  {
    name: 'Bob',
    children: 'Cindy',
    level: 4,
    path: [ 0, 1, 3, 4, 1 ],
    isCycle: true
  },
  {
    name: 'Cindy',
    children: [ 'David', 'Don' ],
    level: 2,
    path: [ 0, 1, 3 ]
  },
  {
    name: 'David',
    children: [ 'Bob' ],
    level: 3,
    path: [ 0, 1, 3, 4 ]
  },
  {
    name: 'Bob',
    children: 'Cindy',
    level: 4,
    path: [ 0, 1, 3, 4, 1 ],
    isCycle: true
  },
  { name: 'Don', level: 3, path: [ 0, 1, 3, 5 ] },
  { name: 'Bill', children: [], level: 1, path: [ 0, 2 ] }
]

添加了 path 和 level 信息后，生成输出或进行其他转换就变得非常简单。

arr = connectBy(myArray, function (val) { return val.name == 'Alice'}, ['name', 'children']);

console.log(arr.map(x => ' '.repeat(2 * x.level) + x.name).join('\n'))

Alice
  Bob
    Cindy
      David
      Don
  Bill


console.log(arr.map(x => x.path.map(m => myArray[m].name).join(' -> ')).join('\n'))

Alice
Alice -> Bob
Alice -> Bob -> Cindy
Alice -> Bob -> Cindy -> David
Alice -> Bob -> Cindy -> Don
Alice -> Bill

它也同样适用于反向关系

myArray = [
   { name: 'Alice' },
   { name: 'Bob', parent: 'Alice' },
   { name: 'Bill', parent: 'Alice' },
   { name: 'Cindy', parent: 'Bob' },
   { name: 'David', parent: 'Cindy' },
   { name: 'Don', parent: 'Cindy' }
]
arr = connectBy(myArray, (val) => { return val.parent == null }, ['parent', 'name']);

或者在一对多关系的场景中：

myArray = [
   { name: 'Adam', children: ['Britney'] },
   { name: 'Alice', children: ['Britney'] },
   { name: 'Britney' }
]

arr = connectBy(myArray, (x) => { return x.children != null }, ['name', 'children']);
console.log(arr.map(x => ' '.repeat(2 * x.level) + x.name).join('\n'))

Adam
  Britney
Alice
  Britney

更新

这里给出一个不会修改输入数组的版本，path 包含来自输入的项：

function connectBy(array, startWith, connectWith, path = [], level = 0) {
   arr = [];
   for (let item of array)
      arr.push({ [connectWith[0]]: item[connectWith[0]], [connectWith[1]]: item[connectWith[1]] });
   const filterFn = typeof startWith == 'function' ?
      startWith :
      function (x) {
         const children = startWith[startWith.length - 1][connectWith[1]];
         return Array.isArray(children) ? children.includes(x[connectWith[0]]) : children == x[connectWith[0]];
      };
   for (let item of arr.filter(filterFn)) {
      if (path.includes(arr.indexOf(item)))
         item.isCycle = true;         
      item.level = level;
      item.path = path.concat(arr.indexOf(item));
      typeof startWith == 'function' ? startWith = [item] : startWith.push(item);
      if (!item.isCycle)
         startWith = connectBy(arr, startWith, connectWith, item.path, level + 1);
   }
   if (level == 0) {
      // Replace indices by original objects
      for (let item of startWith)
         item.path = item.path.filter( x => x >= 0).map( x => array[x] )
   }
   return startWith;
}