поиск дерева массива javascript сохраняет узел и родителей

Question

Попытка реализовать функцию поиска по дереву, которая принимает массив (древовидную структуру) и ключевое слово string, возвращает массив дерева, но сохраняет только совпадающие узлы и их родителей.

function search(nodes, keyword){

}



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"
        }
      ] }
    ]
  },
];

Ожидаемый вывод будет дерево со значениями узлов, содержащих «1-1-2-1» и его родителей, как показано ниже

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



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

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 search(nodes, value) {
    var result;

    nodes.some(o => {
        var children;
        if (o.value === value) {
            return result = o;
        }
        if (o.children && (children = search(o.children, value))) {
            return result = Object.assign({}, o, { children });
        }
    });

    return result;
}


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" }] }] }];

console.log(search(nodes, "1-1-2-1"));

.as-console-wrapper { max-height: 100% !important; top: 0; }