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"的对象.

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

谢谢.

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