algorithm - 如何索引分层数据？

Question

我有一些可以通过两种数据结构表示的分层数据。

第一个是如下所示的多级 JSON 对象:

[
    { 
        "text": "Item 1, "children": [
            {"text": "Nested item 1"}, 
            {"text": "Nested item 2"}] 
    },
    {
        "text": "Item 2", "children": []
    }
]

而第二个结构是一个数组。此数组的项目由 id-parentId 绑定(bind)。

[
    {id: 1, text: "Item 1", parentId: null},
    {id: 2, text: "Nested item 1", parentId: 1}
]

我需要通过一些子串来过滤这些数据。

为了实现这个功能，我想创建一些搜索索引。然后为创建的索引提供过滤操作。

创建搜索索引的主要原因是使用单一过滤算法而不是两种不同的方法来过滤分层数据和 id-parentId 列表。

那么，问题是搜索索引应该是什么格式？目前，我使用这样的东西:

[
    {id: 1, text: "item 1", parentKey: null, childrenKeys: [2,3]},
    {id: 2, text: "child 1", parentKey: 1, childrenKeys: []},
    {id: 3, text: "child 2", parentKey: 1, childrenKeys: []}  
]

优点:每个项目都有指向父项和子项的链接。

缺点:如果源数据结构是层次结构，我必须手动为项目生成键。

Answer 1

只需同时处理两种格式，处理映射到单一格式的麻烦是不值得的。

下面我使用了 Array.prototype.reduce 函数(我可以使用 Array.prototype.filter，但是我不得不连接递归调用的结果数组和/或将函数参数添加到绑定(bind))。

JSFiddle http://jsfiddle.net/5q4cdevt/

/* @this {string} search value */ 
function reduceContains(result, obj) {
    if(obj.text.indexOf(this) >= 0) { 
        result.push(obj); 
    }
    if(obj.children) {
        obj.children.reduce(reduceContains.bind(this), result);
    }
    return result;
}

console.log([
    { 
        "text": "Item 1", "children": [
            {"text": "Nested item 1"}, 
            {"text": "Nested item 2"}] 
    },
    {
        "text": "Item 2", "children": []
    }
].reduce(reduceContains.bind("Nested"), []));

console.log([
    {id: 1, text: "Item 1", parentId: null},
    {id: 2, text: "Nested item 1", parentId: 1}
].reduce(reduceContains.bind("Nested"), []));