javascript 树状搜寻 数组

Question

前端上的需求,需要写一个搜寻的 function 来遍历这个树，

function search(nodes, keyword){
//预期输入 如下方的 `const nodes`
}

const searchedNodes = search(nodes, "1-1-2-1"); 
// 预期要输出包含 "1-1-2-1"的所有节点以及该节点的父节点
/*
searchedNodes 应该要相等于
[
    {
    value: "1-1",
    children: [
      { value: "1-1-2", children:[
        {
          value: "1-1-2-1",
          children: [
            { value: "1-1-2-1-1" }
          ]
        }
      ] }
    ]
  }
]
*/

const nodes = [
  {
    value: "1-1",
    children: [
      { value: "1-1-1"},
      { value: "1-1-2", children:[
        {
          value: "1-1-2-1",
          children: [
            { value: "1-1-2-1-1" },
            { value: "1-1-2-1-2" }
          ]
        },
        {
          value: "1-1-2-2"
        }
      ] }
    ]
  },
  {
    value: "1-2",
    children: [
      { value: "1-2-1"},
      { value: "1-2-2", children:[
        {
          value: "1-2-2-1",
          children: [
            { value: "1-2-2-1-1" },
            { value: "1-2-2-1-2" }
          ]
        },
        {
          value: "1-2-2-2"
        }
      ] }
    ]
  },
];

请问这样的树搜寻应该要怎麽完成呢？

2018-06-26 更新

昨晚自己折騰了一會 寫了一個 DFS 的版本 效能似乎不太好 但堪用

const search = (nodes, keyword) => {
    let newNodes = [];
    for (let n of nodes) {
      if (n.children) {
        const nextNodes = this.keywordFilter(n.children, keyword);
        if (nextNodes.length > 0) {
          n.children = nextNodes;
        } else if (n.label.toLowerCase().includes(keyword.toLowerCase())) {
          n.children = nextNodes.length > 0 ? nextNodes : [];
        }
        if (
          nextNodes.length > 0 ||
          n.label.toLowerCase().includes(keyword.toLowerCase())
        ) {
        
          newNodes.push(n);
        }
      } else {
        if (n.label.toLowerCase().includes(keyword.toLowerCase())) {
          newNodes.push(n);
        }
      }
    }
    return newNodes;
  };

Answer 1

大概写了一下：

function compare(value, keyword){
    if(value === keyword){
        return 2;
    }
    if(new RegExp('^' + value).test(keyword)){
        return 1;
    }
    return 0;
}

function walk(node, keyword){

    let isFind = false;
    const path = [];
    let children = null;

    function dfs(node, keyword){
        if(compare(node.value, keyword) === 1){
            path.push(node.value);
            node.children && node.children.forEach(childNode => {
                dfs(childNode, keyword);
            });
        }
        if(compare(node.value, keyword) === 2) {
            node.children && (children = node.children);
            isFind = true;
        }
    }

    dfs(node, keyword);

    return {
        isFind,
        path,
        children
    }
}

function generateObj(pathArr, keyword, children){
    const resObj = {};
    let tempObj = resObj;
    pathArr.forEach(path => {
        tempObj.value = path;
        tempObj.children = [{}];
        tempObj = tempObj.children[0];
    });
    tempObj.value = keyword;
    children && (tempObj.children = children);
    return resObj;
}

function search(nodes, keyword){
    const searchedNodes = [];
    nodes.forEach(node => {
        const { isFind = false, path, children = null } = walk(node, keyword);
        if(isFind){
            searchedNodes.push(generateObj(path, keyword, children));
        }
    });
    return searchedNodes;
}

const nodes = [
  {
    value: "1-1",
    children: [
      { value: "1-1-1"},
      { value: "1-1-2", children:[
        {
          value: "1-1-2-1",
          children: [
            { value: "1-1-2-1-1" },
            { value: "1-1-2-1-2" }
          ]
        },
        {
          value: "1-1-2-2"
        }
      ] }
    ]
  },
  {
    value: "1-2",
    children: [
      { value: "1-2-1"},
      { value: "1-2-2", children:[
        {
          value: "1-2-2-1",
          children: [
            { value: "1-2-2-1-1" },
            { value: "1-2-2-1-2" }
          ]
        },
        {
          value: "1-2-2-2"
        }
      ] }
    ]
  },
];

const searchedNodes = search(nodes, "1-1-2-1"); 

Answer 2

你给的期望数据和 问题描述有歧义啊，

  children: [
            { value: "1-1-2-1-1" },
            { value: "1-1-2-1-2" }
          ]

中的{ value: "1-1-2-1-2" }也是符合1-1-2-1的啊