Блог

Мне нужна помощь в написании рекурсивной функции javascript для достижения чего-то, но я действительно изо всех сил пытаюсь этого добиться. Может кто-нибудь, пожалуйста, помогите мне или помогите мне в этом.

У меня есть вложенное дерево примерно такого типа: Group1 имеет дочернюю Group2, а Group2 имеет дочернюю Group3. У Group3 нет дочернего элемента.

 [
  {
    name: "Group1",
    children: [{
      name: "Group2",
      children: [{
        name: "Group3"
        children: []
      }],
    }]
  },
 {
   name: "Group5",
   children: [],
 },
 {
  name: "Group6",
  children: [],
 },
 {
  name: "Group7",
  children: [{
    name: "Group 10",
    children: [
        {
            name: 'Group2'
            children: [{
        name: "Group3"
        children: []
      }], 
        }
    ]
  }],
 }
]
 

Если я ищу Group2, функция должна возвращать все родительские и дочерние элементы отдельно в массиве. Как я могу этого добиться.

Пример:

Ввод: «Group2»

Вывод:

 [
   {
      name: "Group1",
      children:[
         {
            name:"Group2",
            children :[
               {
                  name:"Group3",
                  children:[]
               }
            ]
         }
      ]
   },
   {
      name:"Group2",
      children: [
         {
            name:"Group3",
            children:[]
         }
      ]
   },
   {
      name:"Group3",
      children:[]
   },
   {
      name:"Group7",
      children :[
         {
            name:"Group10",
            children:[
               {
                  name:"Group2",
                  children: [
                     {
                        name:"Group3",
                        children :[]
                     }
                  ]
               }
            ]
         }
      ],
   },    
   {
     name:"Group10",
     children:[
            {
               name:"Group2",
               children:[
                  {
                     name:"Group3",
                     children":[]
                  }
               ]
            }
      ]
   }
]
 

Если я ищу ‘Group2’, он должен предоставить мне полный узел отдельно в списке, в котором существует этот термин. Например: ‘Group 2’ является дочерним элементом ‘Group 1’, поэтому полное дерево узлов должно быть в списке [Group1, Group2, Group3], а затем ‘Group2’ также является дочерним элементом ‘Group10’, который также является дочерним элементом ‘Group7’, поэтому объединение полного семейства для этого [Group7,Группа10, Группа2, Группа3]. Таким образом, полный вывод должен быть похож на все отдельные узлы [Group1, Group2, Group3, Group7, Group10]. Имеет ли это смысл??

Любая помощь будет оценена.

Я писал код примерно так, это работает, но не знаю, как сделать это лучше.

   const groups = this.props.groups;
  const filter = (group: Group) => group.name.toLowerCase().includes(searchTerm);
  if (this.state.searchTerm !== '') {
      groups = groups.filter(filter);
      groups = this.groupHierarchy(groups);
  }

  private groupHierarchy = (filteredGroups: Group[]) => {
    const groups: Group[] = filteredGroups;
    groups.map((filteredGroup: Group) =>
      this.addAllChildren(filteredGroup, groups));
    groups.map((filteredGroup: Group) =>
      this.addAllParents(filteredGroup, groups));
    return groups;
  }

  private addAllChildren = (filteredGroup: Group, childGroups: Group[]) => {
    const groups = childGroups;
    if (filteredGroup.children) {
      filteredGroup.children.map((child: Group) => {
        if (!groups.find(a => a.id === child.id)) {
          groups.push(child);
        }
        this.addAllChildren(child, groups);
      });
    }
    return groups;
  }

  private addAllParents = (filteredGroup: Group, parentGroups: Group[]) => {
    const groups = parentGroups;
    if (filteredGroup.parent amp;amp; filteredGroup.parent.id) {

      const parentGroup = this.props.groups.find(group => group.id === filteredGroup.parent!.id)!;
      if (!groups.find(a => a.id === parentGroup.id)) {
        groups.push(parentGroup);
      }
      this.addAllParents(parentGroup, groups);
    }
    return groups;
  }
  
 

Эта версия создает общие функции для проверки, соответствует ли узел или один из его потомков общему предикату, и, используя это, для сбора всех узлов, соответствующих предикату, вместе со всеми их предками и дочерними элементами.

Используя последнее, мы пишем простую функцию, которая принимает целевое имя и возвращает функцию, которая найдет все узлы со name свойством, соответствующим целевому, вместе со всеми их предками и дочерними элементами:

 const hasMatch = (pred) => ({children = [], ...rest}) =>
  pred (rest) || children .some (hasMatch (pred))

const collectFamily = (pred) => (xs) => 
  xs .flatMap (
    x => pred(x) 
      ? [x, ...(x.children || [])] 
    : hasMatch (pred) (x) 
      ? [x, ...collectFamily (pred) (x.children || [])]
    : []
  )

const collectFamilyByName = (target) => 
  collectFamily((({name}) => name == target))

const log = (fn) => (inputs) => // JSON.stringify avoids StackOverflow console artifacts
  inputs .forEach (o => console .log (JSON .stringify (fn (o), null, 2)))

const inputs = [
  [{name: "Group 1", children: [{name: "Group 2", children: [{name: "Group 3", children: []}]}]}, {name: "Group 5", children: []}],
  [{name: "Group 1", children: [{name: "Group 2", children: [{name: "Group 3", children: []}]}]}, {name: "Group 5", children: [{name: 'Group 2', children: []}]}],
]

log (collectFamilyByName ('Group 2')) (inputs) 

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

У меня есть два примера. Первый — это вопрос из вопроса. Второй, следующий за комментарием к другому ответу, добавляет к 'Group 5' объекту дочерний элемент 'Group 2' , и он собирается, как я полагаю, вы хотите.

Код довольно прост, но я вижу два потенциальных недостатка. Во-первых, он повторяется отдельно по дереву для тестирования и сбора. Я уверен, что есть относительно простой способ их объединения, но я не вижу его сразу. Во-вторых, не удастся собрать потомков дочерних узлов, которые также имеют правильное имя. Он останавливается на их дочерних элементах. Опять же, я полагаю, что для этого есть быстрое решение, но я не вижу его в данный момент.

Обновление — объяснение кода

Комментарий подразумевал, что этот код может использовать объяснение. Вот попытка

Сначала мы рассмотрим простейшую функцию, основную, collectFamilyByName :

 const collectFamilyByName = (target) => 
  collectFamily((({name}) => name == target))
 

Эта функция принимает target строку и вызывает collectFamily передачу функции, которая ее использует target . Мы еще не знаем, что collectFamily будет делать; мы просто знаем, что он принимает функцию-предикат (возвращающую true или false ) и возвращает нам новую функцию.

Мы могли бы написать это несколькими разными способами. Вот одна альтернатива:

 const testMatch = function (target) {
  return function (element) {
    return element.name == target
  }
}

const collectFamilyByName = function (target) {
  return collectFamily (testMatch (target))
}
 

что путем простой замены было бы эквивалентно

 const collectFamilyByName = function (target) {
  return collectFamily (function (element) {
    return element.name == target
  })
}
 

Используя более современные функции со стрелками для внутренней функции, это стало бы

 const collectFamilyByName = function (target) {
  return collectFamily (element => element.name == target)
}
 

а затем для внешнего:

 const collectFamilyByName = (target) =>
  collectFamily (element => element.name == target)
 

И, наконец, мы можем использовать деструктурирование параметра для удаления element параметра, например:

 const collectFamilyByName = (target) =>
  collectFamily (({name}) => name == target)
 

Теперь, чтобы понять collectFamily , мы должны понять hasMatch . Давайте снова расширим это до стиля ES5:

 const hasMatch = function (pred) {
  return function (element) {
    return pred (element) || 
           element .children .some (function (child) {
             return hasMatch (pred) (child)
           })
  }
}
 

Это стандартный код ES5, почти, но не совсем, эквивалентный приведенной выше версии. Здесь мы принимаем предикат и возвращаем функцию, которая принимает элемент и возвращает логическое значение. Это будет true, если предикат возвращается true для элемента, или, повторяясь для дочерних элементов элемента, если hasMatch передается один и тот же предикат, а затем передается каждому дочернему элементу, возвращает true для любого из них, используя Array.prototype.some .

Это упрощается до приведенного выше, снова используя функции со стрелками и деструктурирование параметров. Единственное отличие заключается в том, что функция ES5 применяет предикат ко всему объекту, а функция ES6 применяет его к копии объекта, который не включает children . Если это нежелательно, мы могли бы пропустить деструкцию параметра здесь, но я думаю, что обычно имеет смысл сделать это таким образом.

Наконец, основная функция collectFamily , которая выглядит следующим образом:

 const collectFamily = (pred) => (xs) => 
  xs .flatMap (
    x => pred(x) 
      ? [x, ...(x.children || [])] 
    : hasMatch (pred) (x) 
      ? [x, ...collectFamily (pred) (x.children || [])]
    : []
  )
 

Я не буду проходить здесь упражнение ES6 -> ES5. Это работает точно так же, как и в двух других. Вместо этого давайте рассмотрим flatMap и синтаксис распространения.

• flatMap это операция над массивами, которая работает очень похоже map , за исключением того, что она ожидает, что функция вернет массив объектов при каждом вызове, которые затем объединяются в один массив.

   [10, 20, 30] .flatMap ((n) => [n, n   1, n   2])
  //=> [10, 11, 12, 20, 21, 22, 30, 31, 32]
   

• синтаксис spread использует токен ... для распространения содержимого массива
  (или объекта, здесь не относящегося к делу) в другой массив. Так что, если xs удерживается [1, 2, 3] , тогда [5, 10, ...xs, 20] это даст [5, 10, 1, 2, 3, 20] результат.

Зная это, мы можем понять collectFamily . Он принимает предикат (который, как мы уже знаем, будет соответствовать объектам, name свойство которых имеет то же значение, что и наше целевое значение) и возвращает функцию, которая принимает массив объектов. Он вызывает flatMap для этого массива, передавая функцию, поэтому мы знаем, что эта функция должна возвращать массив значений, учитывая один элемент в исходном массиве.

Если бы я переписал это, я мог бы изложить это немного по-другому, чтобы сделать тело этой функции немного более понятным, возможно, так:

 const collectFamily = (pred) => (xs) => 
  xs .flatMap (
    (x) => 
      pred (x) 
        ? [x, ...(x .children || [])] 
      : hasMatch (pred) (x) 
        ? [x, ...collectFamily (pred) (x .children || [])]
      : []
  )
 

И функция, которой передается значение массива с именем параметра x , будет иметь это тело:

       pred (x) 
        ? [x, ...(x.children || [])] 
      : hasMatch (pred) (x) 
        ? [x, ...collectFamily (pred) (x.children || [])]
      : []
 

Мы возвращаем одно из трех разных значений.

В первом случае, если предикат соответствует нашему текущему значению (опять же, помните в этом случае, что если name свойство x соответствует целевому, например 'Group 2' ), то мы возвращаем массив, включающий x и все его дочерние элементы. Мы используем || [] так, чтобы, если x .children бы они не были определены, у нас все равно был бы итеративный объект для распространения в наш массив. Это не имеет значения для предоставленных выборочных данных, но полезно во многих случаях.

Во втором случае, если у нас есть совпадение где-то, вложенное более глубоко, как сообщает hasMatch , мы возвращаем массив, включающий этот узел, и все результаты, найденные рекурсивным вызовом collectFamily с тем же предикатом для списка дочерних элементов (опять же, по умолчанию используется пустой массив, если они не существуют.)

И в третьем случае, если ни одно из них не является истинным, мы просто возвращаем пустой массив.

Итак, вот как это работает. Здесь нет никакой магии, но если вы новичок в языке, некоторые из более современных функций могут показаться немного непонятными. Я обещаю, однако, что с небольшой практикой они станут второй натурой. Они значительно упрощают код, и, как только вы привыкнете к синтаксису, мне кажется, их также намного легче читать.

Вы могли бы использовать рекурсивный подход с коротким замыканием при поиске.

Чтобы получить все родительские элементы, функция содержит другой параметр для посещенных родительских элементов.

 const
    getFromTree = (tree, name, parents = []) => {
        let resu<
        tree.some(node => result = node.name === name
            ? [...parents, node, ...node.children]
            : getFromTree(node.children, name, [...parents, node])
        );
        return resu<
    },
    tree = [{ name: "Group 1", children: [{ name: "Group 2", children: [{ name: "Group 3", children: [] }] }] }, { name: "Group 5", children: [] }];

console.log(getFromTree(tree, "Group 1"));
console.log(getFromTree(tree, "Group 2"));
console.log(getFromTree(tree, "Group 3"));
console.log(getFromTree(tree, "Group 5")); 

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