JavaScript:如何过滤深度 JSON 对象

Question

我有一组深度 JSON 对象，看起来与此类似:

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，我需要以仅保留包含已定义对象的(子)类别的方式过滤这组对象。

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

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”的对象已删除。

问题是这些对象的深度是可变的和未知的 - 有些对象没有 child ，有些有 child 也有 child 等，任何子类别本身都可以有一个子类别，我基本上需要找到没有 child 的对象已定义 ID 并保留每个 ID 的完整路径的 child 。

谢谢。

Answer 1

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

构建树的部分和过滤副本后，您需要清理原始树。出于记账目的，我在此过程中对原始树进行了变异 - 跟踪哪些分支已被克隆。

编辑:修改代码以过滤树列表，而不仅仅是一棵树

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);