js如何实现多层级数组筛选

Question

现有一个多层级数组，层数不固定，想要通过输入一个关键字，能够将整个数组遍历一遍，然后将与name模糊匹配上的元素筛选出来，而且还要保留其所在的层级结构。

请问有什么好的实现思路么？

    //举例数组结构
    var treeNodeList=[
      {
        "name": "一级A",
        "children": [{
            "name": "一级-1",
            "children": [{
                "name": "一级-1-1",
                "children": [
                    {
                    "name": "一级-1-1-1",
                    "type": "true",
                    },
                    {
                    "name": "一级-1-1-3",
                    "type": "true",
                    }
                ]
            }]
        },
         {
        "name": "二级B",
        "children": [{
            "name": "二级-1",
            "children": [{
                "name": "二级-2-2",
                "children": [
                    {
                    "name": "二级-2-2-2",
                    "type": "true",
                    },
                    {
                    "name": "二级-2-2-1",
                    "type": "true",
                    }
                ]
            }]
        },
         {
        "name": "三级C",
        "children": [{
            "name": "三级-1",
            "children": [{
                "name": "三级-3-1",
                "children": [
                    {
                    "name": "三级-3-3-1",
                    "type": "true",
                    },
                    {
                    "name": "三级-3-3-2",
                    "type": "true",
                    }
                ]
            }]
        },
        ]    
        
  //输入关键字 3 想要筛选出如下结果
   [
      {
        "name": "一级A",
        "children": [{
            "name": "一级-1",
            "children": [{
                "name": "一级-1-1",
                "children": [
                    {
                    "name": "一级-1-1-3",
                    "type": "true",
                    }
                ]
            }]
        },
         {
        "name": "三级C",
        "children": [{
            "name": "三级-1",
            "children": [{
                "name": "三级-3-1",
                "children": [
                    {
                    "name": "三级-3-3-1",
                    "type": "true",
                    },
                    {
                    "name": "三级-3-3-2",
                    "type": "true",
                    }
                ]
            }]
        },
        ]
        
    //输入关键字 A 想要筛选出如下结果    
    [
      {
        "name": "一级A",
        "children": [{
            "name": "一级-1",
            "children": [{
                "name": "一级-1-1",
                "children": [
                    {
                    "name": "一级-1-1-1",
                    "type": "true",
                    },
                    {
                    "name": "一级-1-1-3",
                    "type": "true",
                    }
                ]
            }]
        }
        ]        

Answer 1

var treeNodeList = [{
        "name": "一级A",
        "children": [{
            "name": "一级-1",
            "children": [{
                "name": "一级-1-1",
                "children": [{
                        "name": "一级-1-1-1",
                        "type": "true",
                    },
                    {
                        "name": "一级-1-1-3",
                        "type": "true",
                    }
                ]
            }]
        }]
    },
    {
        "name": "二级B",
        "children": [{
            "name": "二级-1",
            "children": [{
                "name": "二级-2-2",
                "children": [{
                        "name": "二级-2-2-2",
                        "type": "true",
                    },
                    {
                        "name": "二级-2-2-1",
                        "type": "true",
                    }
                ]
            }]
        }]
    },
    {
        "name": "三级C",
        "children": [{
            "name": "三级-1",
            "children": [{
                "name": "三级-3-1",
                "children": [{
                        "name": "三级-3-3-1",
                        "type": "true",
                    },
                    {
                        "name": "三级-3-3-2",
                        "type": "true",
                    }
                ]
            }]
        }]
    }
]

var query = 'A';

var filterObj = function(item){
    if(item.name.indexOf(query) > -1) return true;
    if(item.hasOwnProperty("children")){
        item.children = item.children.filter(function(child){
            if(child.hasOwnProperty("type")){
                return child.name.indexOf(query) > -1;
            }else if(child.hasOwnProperty("children")){
                return filterObj(child);
            }
        })
        if(item.children.length > 0){
            return true;
        }
    }else{
        return child.name.indexOf(query) > -1;
    }
}
var filter = treeNodeList.filter(function(item){
    return filterObj(item);
});

console.log(JSON.stringify(filter));

自己写了几行代码，经测试通过，可供参考。

Answer 2

我之前写过一个多维数组指定子项扁平化函数

/**
 * 多维数组指定子项扁平化函数
 * @param array              要执行的扁平化数组
 * @param childrenKeys       要参与扁平的子键名数组 默认 ['children']
 * @param flattenParent      默认的父数组
 * @param flattenParentKey   被压平后子项父数组存放键名
 * @returns {Array}
 */
function arrayChildrenFlatten(array, {childrenKeys, flattenParent, flattenParentKey} = {}) {
  childrenKeys = childrenKeys || ['children'];
  flattenParent = flattenParent || [];
  flattenParentKey = flattenParentKey || 'flattenParent';
  const result = [];
  array.forEach(item => {
    const flattenItem = JSON.parse(JSON.stringify(item));
    flattenItem[flattenParentKey] = flattenParent;
    result.push(flattenItem);
    childrenKeys.forEach(key => {
      if (item[key] && Array.isArray(item[key])) {
        const children = arrayChildrenFlatten(item[key], {
          childrenKeys,
          flattenParent: [...flattenParent, item],
          flattenParentKey,
        });
        result.push(...children);
      }
    });
  });
  return result;
}

提前把数组用这个函数处理后要筛选就是一个遍历的事情，如果采用的话通过flattenParentKey重新生成树因为我用不到没有现成的 就要靠你自己去写了

Answer 3

深度优先遍历树，剪掉不符合的叶节点，根节点根据是否还有叶节点以及本身是否模糊匹配确定是否保留。模糊匹配的话，可以简单的用字符串距离（余弦距离）来解决之。