Javascript найти глубоко вложенные объекты

Question

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

Допустим, у меня есть следующая структура

[
  {
    label: "first",
    id: 1,
    children: []
  },
  {
    label: "second",
    id: 2,
    children: [
      {
        label: "third",
        id: 3,
        children: [
          {
            label: "fifth",
            id: 5,
            children: []
          },
          {
            label: "sixth",
            id: 6,
            children: [
              {
                label: "seventh",
                id: 7,
                children: []
              }
            ]
          }
        ]
      },
      {
        label: "fourth",
        id: 4,
        children: []
      }
    ]
  }
];

Я хочу найти ту, в которой есть id 6, и если у нее есть дети, верните true, в противном случае false.

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

Answer 1

Параметр JSON.parse reviver или параметр заменителя JSON.stringify можно использовать для проверки всех значений и создания объекта поиска с плоским идентификатором со ссылками на узлы:

var lookup = {}, json = '[{"label":"first","id":1,"children":[]},{"label":"second","id":2,"children":[{"label":"third","id":3,"children":[{"label":"fifth","id":5,"children":[]},{"label":"sixth","id":6,"children":[{"label":"seventh","id":7,"children":[]}]}]},{"label":"fourth","id":4,"children":[]}]}]'

var result = JSON.parse(json, (key, val) => val.id ? lookup[val.id] = val : val);

console.log( 'id: 2, children count:', lookup[2].children.length )
console.log( 'id: 6, children count:', lookup[6].children.length )
console.log( lookup )

Answer 2

Я предлагаю использовать deepdash расширение для lodash:

var id6HasChildren = _.filterDeep(obj,
  function(value, key, parent) {
    if (key == 'children' && parent.id == 6 && value.length) return true;
  },
  { leavesOnly: false }
).length>0;

Вот документы для filterDeep .

И это полный тест для вашего случая.

Answer 3

Вот еще одно решение, использующее recursion и выполняющее его только через один Array.find:

const data = [ { label: "first", id: 1, children: [] }, { label: "second", id: 2, children: [ { label: "third", id: 3, children: [ { label: "fifth", id: 5, children: [] }, { label: "sixth", id: 6, children: [ { label: "seventh", id: 7, children: [] } ] } ] }, { label: "fourth", id: 4, children: [] } ] } ];

const search = (data, id) => {
  var f, s = (d, id) => d.find(x => x.id == id ? f = x : s(x.children, id))	
  s(data, id)
  return f ? f.children.length > 0 : false
}

console.log(search(data, 6))  // True: found with children
console.log(search(data, 7))  // False: found but has no children
console.log(search(data, 15)) // False: not found at all

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

Как только мы найдем (или мы знаем, что у нас нет найденной записи), просто верните дочерние элементы array length или верните false.

Если вы действительно хотите вернуть found object вместо логического значения для children.length:

const data = [ { label: "first", id: 1, children: [] }, { label: "second", id: 2, children: [ { label: "third", id: 3, children: [ { label: "fifth", id: 5, children: [] }, { label: "sixth", id: 6, children: [ { label: "seventh", id: 7, children: [] } ] } ] }, { label: "fourth", id: 4, children: [] } ] } ];

const search = (data, id) => {
  var f, s = (d, id) => d.find(x => x.id == id ? f = x : s(x.children, id))	
  s(data, id)
  return f
}

console.log(search(data, 6))  // returns only the object with id:6
console.log(search(data, 7))  // returns only the object with id: 7
console.log(search(data, 71)) // returns undefined since nothing was found

Answer 4

Вы можете использовать функцию генератора , чтобы рекурсивно повторять узлы и упростить вашу логику для проверки существования, используя Array.prototype.some():

const data = [{label:'first',id:1,children:[]},{label:'second',id:2,children:[{label:'third',id:3,children:[{label:'fifth',id:5,children:[]},{label:'sixth',id:6,children:[{label:'seventh',id:7,children:[]}]}]},{label:'fourth',id:4,children:[]}]}];

function * nodes (array) {
  for (const node of array) {
    yield node;
    yield * nodes(node.children);
  }
}

const array = Array.from(nodes(data));

console.log(array.some(node => node.id === 6 && node.children.length > 0));
console.log(array.some(node => node.id === 7 && node.children.length > 0));

Answer 5

Вы можете сделать это с помощью трех простых функций JavaScript:

// Function to Flatten results
var flattenAll = function(data) {
  var result = [];
  var flatten = function(arr) {
    _.forEach(arr, function(a) {
      result.push(a);
      flatten(a.children);
    });
  };
  flatten(data);
  return result;  
};

// Function to search on flattened array
var search = function(flattened, id) {
  var found = _.find(flattened, function(d) { 
              return d.id == id;
            });
  return found;
};

// Function to check if element is found and have children
var hasChildren = function(element) {
  return element && element.children && element.children.length > 0;
}

// Usage, search for id = 6
hasChildren(search(flattenAll(your_data_object), 6))

Plunker

Answer 6

Поскольку вам нужен только ответ true из false, вы можете использовать some() в рекурсии, эффективно выполняя поиск в глубину и делая его довольно кратким:

let arr = [{label: "first",id: 1,children: []},{label: "second",id: 2,children: [{label: "third",id: 3,children: [{label: "fifth",id: 5,children: []},{label: "sixth",id: 6,children: [{label: "seventh",id: 7,children: []}]}]},{label: "fourth",id: 4,children: []}]}];

function findNested(arr, id) {
    let found = arr.find(node => node.id === id)
    return found 
      ? found.children.length > 0 
      : arr.some((c) => findNested(c.children, id))

} 

console.log(findNested(arr, 6))  // True: found with children
console.log(findNested(arr, 7))  // False: found no children
console.log(findNested(arr, 97)) // False: not found

Answer 7

Вы можете использовать "рекурсию", как показано ниже, чтобы проверить, есть ли у id дети или нет

let arr = [{label: "first",id: 1,children: []},{label: "second",id: 2,children: [{label: "third",id: 3,children: [{label: "fifth",id: 5,children: []},{label: "sixth",id: 6,children: [{label: "seventh",id: 7,children: []}]}]},{label: "fourth",id: 4,children: []}]}];

function hasChildren(arr, id) {
  let res = false
  for (let d of arr) {
    if(d.id == id) return d.children.length > 0
    res = res || hasChildren(d.children, id)
    if(res) return true
  }
  return res
}

console.log('id 4 has children? ', hasChildren(arr, 4))
console.log('id 6 has children? ', hasChildren(arr, 6))

Answer 8

также:

function explore(myArray, searchedId) {
    for (let i=0; i<myArray.length; i++) {
        let el;
        if (myArray[i].id == searchedId) {
            el = myArray[i];
        } else {
            el = explore(myArray[i].children, searchedId);
        }
        if (el) {
            return el.children.length > 0;
        }
    }
}    

Answer 9

Возможно, рекурсивное решение в духе этого может помочь вам? Здесь, узел с предоставленным идентификатором рекурсивно ищется через «потомки» предоставленных входных данных. Если дочерний узел с совпадающим идентификатором найден, возвращается логический результат, основанный на существовании данных в этих узлах children массив:

function nodeWithIdHasChildren(children, id) {
  
  for(const child of children) {

    // If this child node matches supplied id, then check to see if
    // it has data in it's children array and return true/false accordinly
    if(child.id === id) {
    
      if(Array.isArray(child.children) && child.children.length > 0) {
        return true
      }
      else {
        return false
      }
    }
    else {
    
      const result = nodeWithIdHasChildren(child.children, id);

      // If result returned from this recursion branch is not undefined
      // then assume it's true or false from a node matching the supplied
      // id. Pass the return result up the call stack
      if(result !== undefined) {
        return result
      }
    }
  }  
}

const data = [
  {
    label: "first",
    id: 1,
    children: []
  },
  {
    label: "second",
    id: 2,
    children: [
      {
        label: "third",
        id: 3,
        children: [
          {
            label: "fifth",
            id: 5,
            children: []
          },
          {
            label: "sixth",
            id: 6,
            children: [
              {
                label: "seventh",
                id: 7,
                children: []
              }
            ]
          }
        ]
      },
      {
        label: "fourth",
        id: 4,
        children: []
      }
    ]
  }
];



console.log('node 6 has children:', nodeWithIdHasChildren( data, 6 ) )

console.log('node 7 has children:', nodeWithIdHasChildren( data, 7 ) )

console.log('node 100 has children:', nodeWithIdHasChildren( data, 7 ), '(because node 100 does not exist)' )