JavaScript：如何过滤深JSON对象 [英] JavaScript: how to filter deep JSON objects

问题描述

我有一系列深度JSON对象，看起来与此类似：

I have an array of deep JSON objects that look like similarly to this:

var hierarchy = [
  {
    "title": "category 1",
    "children": [
      {"title": "subcategory 1",
        "children": [
          {"id": 1, "title": "name 1"},
          {"id": 2, "title": "name 2"},
          {"id": 3, "title": "name 3"}
        ]
      },
      {"title": "subcategory 2",
        "children": [
          {"id": 1, "title": "name 4"}
        ]
      }
    ]
  },
  {
    "title": "category 2",
    "children": [etc. - shortened for brevity]
  }
];

所以基本上它是一个层次结构 - 有些类别可以包含子类别，其中包含具有一些ID的对象名。我还有一个与最深层次结构级别（没有子级的对象）相关的ID数组，我需要过滤这组对象，使得只包含已定义对象的（子）类别。

So basically it is a hierarchy - there are categories which can have subcategories which contain objects with some IDs and names. I also have an array of IDs that are related to the deepest hierarchy level (objects with no children) and I need to filter this set of objects in such a way that only (sub)categories that contain defined objects remain.

例如，如果我有一个包含两个ID的数组：

So for example if I had an array containing two IDs:

var IDs = [2, 3];

结果将是：

var hierarchy = [
  {
    "title": "category 1",
    "children": [
      {"title": "subcategory 1",
        "children": [
          {"id": 2, "title": "name 2"},
          {"id": 3, "title": "name 3"}
        ]
      }
    ]
  }
];

即。整体而言，整个'类别2'对象被删除，整个'子类别2'被删除，对象ID'1'被删除。

i.e. the whole, the whole 'category 2' object removed, the whole 'subcategory 2' removed, object with ID '1' removed.

问题在于深度那些对象是变量和未知的 - 有些对象没有子节点，有些对象也有子节点等，任何子类别本身都可以有子类别，我基本上需要找到没有子节点定义了ID的对象并保持整个路径对于他们每个人。

The problem is that the depth of those objects is variable and unknown - some objects have no children, some have children that also have children etc., any subcategory can can itself have a subcategory and I basically need to find object with no children that have defined IDs and keep the whole path to each of them.

谢谢。

推荐答案

基本上，执行树的深度优先遍历，在每个节点上调用回调函数。如果该节点是叶节点并且它的ID出现在列表中，则克隆导致该叶子的分支，但不重新克隆分支的任何部分已经克隆过。

Basically, perform a depth first traversal of your tree invoking a callback function on each node. If that node is a leaf node and it's ID appears in your list then clone the branch that leads to that leaf, but don't re-clone any part of the branch that was already cloned.

一旦构建了树的部分和过滤副本，就需要清理原始文件。为了记账，我在原始树中进行了突变 - 跟踪已经克隆的分支。

Once you have constructed the partial and filtered copy of your tree you need to cleanup the original. I mutated the original tree in the process for book-keeping purposes - tracking which branches had already been cloned.

编辑：修改后的代码进行过滤树木而不仅仅是一棵树

modified code to filter list of trees instead of just a single tree

var currentPath = [];

function depthFirstTraversal(o, fn) {
    currentPath.push(o);
    if(o.children) {
        for(var i = 0, len = o.children.length; i < len; i++) {
            depthFirstTraversal(o.children[i], fn);
        }
    }
    fn.call(null, o, currentPath);
    currentPath.pop();
}

function shallowCopy(o) {
    var result = {};
    for(var k in o) {
        if(o.hasOwnProperty(k)) {
            result[k] = o[k];
        }
    }
    return result;
}

function copyNode(node) {
    var n = shallowCopy(node);
    if(n.children) { n.children = []; }
    return n;
}

function filterTree(root, ids) {
    root.copied = copyNode(root); // create a copy of root
    var filteredResult = root.copied;

    depthFirstTraversal(root, function(node, branch) {
        // if this is a leaf node _and_ we are looking for its ID
        if( !node.children && ids.indexOf(node.id) !== -1 ) {
            // use the path that the depthFirstTraversal hands us that
            // leads to this leaf.  copy any part of this branch that
            // hasn't been copied, at minimum that will be this leaf
            for(var i = 0, len = branch.length; i < len; i++) {
                if(branch[i].copied) { continue; } // already copied

                branch[i].copied = copyNode(branch[i]);
                // now attach the copy to the new 'parellel' tree we are building
                branch[i-1].copied.children.push(branch[i].copied);
            }
        }
    });

    depthFirstTraversal(root, function(node, branch) {
        delete node.copied; // cleanup the mutation of the original tree
    });

    return filteredResult;
}

function filterTreeList(list, ids) {
    var filteredList = [];
    for(var i = 0, len = list.length; i < len; i++) {
        filteredList.push( filterTree(list[i], ids) );
    }
    return filteredList;
}

var hierarchy = [ /* your data here */ ];
var ids = [1,3];

var filtered = filterTreeList(hierarchy, ids);

这篇关于JavaScript：如何过滤深JSON对象的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！