javascript - 根据特定规则获取自定义数组列表的层级顺序

Question

我想从下面的数组列表中获取层次顺序。

var data = [
   ['','dog'],
   ['dog','cat'],
   ['dog','fish'],
   ['dog','ark'],
   ['dog','folder'],
   ['cat','blue'],
   ['cat','pencil'],
   ['cat','mouse'],
   ['fish','stencil'],
   ['fish','bread'],
   ['fish','milk'],
   ['fish','love'],
   ['mouse','tv'],
   ['mouse','oil'],
   ['mouse','car'],
   ['milk','dough'],
   ['milk','butter'],
   ['car','truck']
];

'计算'的方法是从第一个数组开始

['','dog']

注意:我将索引 0('')称为“父”，索引 1('狗')称为“子”

所以我们想找到以 'dog' 为父项的数组，然后检查这些数组以查看其子项是否有任何父项，如果没有，则继续下一个。 (真的希望这是有道理的)

下面是我上面数据集的排序结果。

var result = ['dog', 'cat', 'blue', 'pencil', 'mouse', 'tv', 'oil', 'car', 'truck', 'fish', 'stencil', 'bread', 'milk', 'dough', 'butter', 'love', 'ark', 'folder'];

我曾尝试使用一些非常糟糕的 while 循环和 .filters() 来获取包含子索引作为父索引的数组，但失败了。

如果有人能对此提供一些见解或返回最终结果的方法，我将不胜感激，因为我无法手动解决这个问题。

Answer 1

我认为这是您的算法。

1. 将源数组转换为嵌套对象，使用引用传递有效关联父子。

这是一个 ES6 实现:

function pairsToIndex(pairs) {
    return pairs.reduce((index, pair, i, list) => {
        let [ parent , child ] = pair;

        let parent_exists = index.hasOwnProperty(parent);
        let child_exists = index.hasOwnProperty(child);

        if(!parent_exists) {
            index[parent] = { key: parent , children: [] };
        }

        if(!child_exists) {
            index[child] =  { key: child  , children: [] };
        }

        // now, ensure that parent-child relationship is captured
        let rel_captured = Boolean( index[parent].children.find((c) => c.key === child) );

        if(!rel_captured) {
            index[parent].children.push( index[child] );
        }

        return index;
    }, {});
}

let data = [
    ['','dog'],
    ['dog','cat'],
    ['dog','fish'],
    ['dog','ark'],
    ['dog','folder'],
    ['cat','blue'],
    ['cat','pencil'],
    ['cat','mouse'],
    ['fish','stencil'],
    ['fish','bread'],
    ['fish','milk'],
    ['fish','love'],
    ['mouse','tv'],
    ['mouse','oil'],
    ['mouse','car'],
    ['milk','dough'],
    ['milk','butter'],
    ['car','truck']
];

let x = pairsToIndex(data);
console.log(x);

在浏览器的开发控制台中运行该代码。当您深入了解对象 x 时，您会注意到每个“子级”都充当指向 x 的另一个顶级属性的符号链接(symbolic link)。实际上，每个“ child ”都是通往该对象内其他地方的门户。这种按引用传递的使用为我们准备了第 2 步...

---

1. 通过以深度优先模式递归遍历该对象并返回每个节点的 key 属性来序列化该对象。

所以，这里有一个简短的例子:

function listNode(node) {
    return Array.prototype.concat.apply( [node.key] , node.children.map(listNode) );
}

let out = listNode(x['']); // choosing the entry point to the hierarchy
console.log(out);

请注意，我必须使用 apply 来避免创建一堆嵌套的 1 元素数组(即使它们会被正确排序)。这可以用 _.flatten 之类的东西解决，但在这种情况下，对语言了解更多一点就不需要整个库了。

另请注意，listNode 在技术上对层次结构的子树进行操作。我告诉它从“根”节点开始，您建议它在原始数据集中由空字符串标识。但是，您可以要求它通过将不同的起点传递给它来序列化树的一个子集，例如listNode( x['cat'] ) 或 listNode( x['fish'] )。

最后，这个算法是无限递归的。如果你给它一个非常大的数据集，浏览器会停止这个脚本。其他 JS 环境(如 nodejs 或 react-native)不会这样做。

---

此时，out 是一个数组，它按照您希望的顺序列出原始 data 数组中的每个值。