javascript 樹(shù)狀搜尋數(shù)組

前端上的需求,需要寫(xiě)一個(gè)搜尋的 function 來(lái)遍歷這個(gè)樹(shù)，

function search(nodes, keyword){
//預(yù)期輸入 如下方的 `const nodes`
}

const searchedNodes = search(nodes, "1-1-2-1"); 
// 預(yù)期要輸出包含 "1-1-2-1"的所有節(jié)點(diǎn)以及該節(jié)點(diǎn)的父節(jié)點(diǎn)
/*
searchedNodes 應(yīng)該要相等于
[
    {
    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"
        }
      ] }
    ]
  },
];

請(qǐng)問(wèn)這樣的樹(shù)搜尋應(yīng)該要怎麼完成呢？

2018-06-26 更新

昨晚自己折騰了一會(huì) 寫(xiě)了一個(gè) 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;
  };

回答

編輯回答

你的瞳

你給的期望數(shù)據(jù)和問(wèn)題描述有歧義啊，

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

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

2018年2月8日 14:58

編輯回答

荒城

大概寫(xiě)了一下：


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

2018年3月26日 13:37