Поиск детей с идентификатором в JavaScript - PullRequest
Новая
       2

Поиск детей с идентификатором в JavaScript

0 голосов
/ 08 ноября 2018

У меня есть такой массив: 

[
    {
        id: "1233",
        parentId: "5436"
    },
    {
        id: "5436",
        parentId: "5664"
    },
    ...
]

это изображение дерева с детьми и родителями. Таким образом, это фактически массив объектов, каждый из которых имеет идентификатор и родительский идентификатор.

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

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

Я использовал следующую функцию для поиска: 

function searchForChildren(parentId, tree) {
const children = [];
tree.forEach(element => {
    if (element.parentUid === parentId) {
        children.push(element);
    }
});
for (const child of children) {
    const childrenTemp = searchForChildren(child.id, tree);
    children.concat(childrenTemp);
}
return children;
}

Пример данных будет выглядеть так: 

 0: {id: "7020441", parentUid: "2442074"}
 1: {id: "7020438", parentUid: "2442077"}
 2: {id: "7020435", parentUid: "2442079"}
 3: {id: "7020437", parentUid: "2442079"}
 4: {id: "7013749", parentUid: "2442086"}
 5: {id: "7013750", parentUid: "2442086"}
 6: {id: "7013752", parentUid: "2442086"}
 7: {id: "7013753", parentUid: "2442086"}
 8: {id: "7013751", parentUid: "2442086"}
 9: {id: "7013746", parentUid: "2442089"}
 10: {id: "7013747", parentUid: "2442089"}
 11: {id: "7013765", parentUid: "2442092"}
 12: {id: "7013767", parentUid: "2442092"}
 13: {id: "7013768", parentUid: "2442092"}
 14: {id: "7013765", parentUid: "2442092"}
 15: {id: "7013767", parentUid: "2442092"}
 16: {id: "7013768", parentUid: "2442092"}
 17: {id: "7013765", parentUid: "2442092"}
 18: {id: "7013767", parentUid: "2442092"}
 19: {id: "7013768", parentUid: "2442092"}
 20: {id: "7013765", parentUid: "2442092"}
 21: {id: "7013767", parentUid: "2442092"}
 22: {id: "7013768", parentUid: "2442092"}
 23: {id: "7013765", parentUid: "2442092"}
 24: {id: "7013767", parentUid: "2442092"}
 25: {id: "7013768", parentUid: "2442092"}
 26: {id: "7013765", parentUid: "2442092"}
 27: {id: "7013767", parentUid: "2442092"}
 28: {id: "7013768", parentUid: "2442092"}
 29: {id: "7013765", parentUid: "2442092"}
 30: {id: "7013767", parentUid: "2442092"}
 31: {id: "7013768", parentUid: "2442092"}
 32: {id: "7013765", parentUid: "2442092"}
 33: {id: "7013767", parentUid: "2442092"}
 34: {id: "7013768", parentUid: "2442092"}
 35: {id: "7013765", parentUid: "2442092"}
 36: {id: "7013767", parentUid: "2442092"}
 37: {id: "7013768", parentUid: "2442092"}
 38: {id: "7013765", parentUid: "2442092"}
 39: {id: "7013767", parentUid: "2442092"}
 40: {id: "7013768", parentUid: "2442092"}
 41: {id: "7013765", parentUid: "2442092"}
 42: {id: "7013767", parentUid: "2442092"}
 43: {id: "7013768", parentUid: "2442092"}
 44: {id: "7013765", parentUid: "2442092"}
 45: {id: "7013767", parentUid: "2442092"}
 46: {id: "7013768", parentUid: "2442092"}
 47: {id: "2442074", parentUid: ""}
 48: {id: "2442075", parentUid: "2442074"}
 49: {id: "2442076", parentUid: "2442075"}
 50: {id: "2442077", parentUid: "2442076"}
 51: {id: "2442078", parentUid: "2442076"}
 52: {id: "2442079", parentUid: "2442075"}
 53: {id: "2442080", parentUid: "2442075"}
 54: {id: "2442081", parentUid: "2442075"}
 55: {id: "2442082", parentUid: "2442074"}
 56: {id: "2442083", parentUid: "2442074"}
 57: {id: "2442084", parentUid: "2442074"}
 58: {id: "2442085", parentUid: "2442084"}
 59: {id: "2442086", parentUid: "2442084"}
 60: {id: "2442087", parentUid: "2442084"}
 61: {id: "2442088", parentUid: "2442084"}
 62: {id: "2442089", parentUid: "2442088"}
 63: {id: "2442090", parentUid: "2442074"}
 64: {id: "2442091", parentUid: "2442090"}
 65: {id: "2442092", parentUid: "2442091"}
 66: {id: "2442092", parentUid: "2442091"}
 67: {id: "2442092", parentUid: "2442091"}
 68: {id: "2442091", parentUid: "2442090"}
 69: {id: "2442092", parentUid: "2442091"}
 70: {id: "2442092", parentUid: "2442091"}
 71: {id: "2442092", parentUid: "2442091"}
 72: {id: "2442091", parentUid: "2442090"}
 73: {id: "2442092", parentUid: "2442091"}
 74: {id: "2442092", parentUid: "2442091"}
 75: {id: "2442092", parentUid: "2442091"}
 76: {id: "2442091", parentUid: "2442090"}
 77: {id: "2442092", parentUid: "2442091"}
 78: {id: "2442092", parentUid: "2442091"}
 79: {id: "2442092", parentUid: "2442091"}
 80: {id: "2442093", parentUid: "2442090"}
 81: {id: "2442094", parentUid: "2442074"}
 82: {id: "2442095", parentUid: "2442074"}

Ответы [ 2 ]

0 голосов
/ 08 ноября 2018

У вас была правильная идея использовать рекурсию. Ваша единственная ошибка в том, что вы используете children.concat(childrenTemp), который ничего не делает с исходным массивом. Вместо этого используйте children.push(...childrenTemp).

Вот исправленная версия: 

const data = [{
    id: "2442086",
    parentUid: "2442074"
  },
  {
    id: "7020438",
    parentUid: "2442077"
  },
  {
    id: "7020435",
    parentUid: "2442079"
  },
  {
    id: "7020437",
    parentUid: "2442079"
  },
  {
    id: "2442092",
    parentUid: "2442086"
  },
  {
    id: "7013750",
    parentUid: "2442086"
  },
  {
    id: "7013752",
    parentUid: "2442086"
  },
  {
    id: "7013753",
    parentUid: "2442086"
  },
  {
    id: "7013751",
    parentUid: "2442086"
  },
  {
    id: "7013746",
    parentUid: "2442089"
  },
  {
    id: "7013747",
    parentUid: "2442089"
  },
  {
    id: "7013765",
    parentUid: "2442092"
  },
  {
    id: "7013767",
    parentUid: "2442092"
  },
  {
    id: "7013768",
    parentUid: "2442092"
  },
  {
    id: "7013765",
    parentUid: "2442092"
  },
  {
    id: "7013767",
    parentUid: "2442092"
  },
  {
    id: "7013768",
    parentUid: "2442092"
  },
  {
    id: "7013765",
    parentUid: "2442092"
  },
  {
    id: "7013767",
    parentUid: "2442092"
  },
  {
    id: "7013768",
    parentUid: "2442092"
  },
  {
    id: "7013765",
    parentUid: "2442092"
  },
  {
    id: "7013767",
    parentUid: "2442092"
  },
  {
    id: "7013768",
    parentUid: "2442092"
  },
  {
    id: "7013765",
    parentUid: "2442092"
  },
  {
    id: "7013767",
    parentUid: "2442092"
  },
  {
    id: "7013768",
    parentUid: "2442092"
  },
  {
    id: "7013765",
    parentUid: "2442092"
  },
  {
    id: "7013767",
    parentUid: "2442092"
  }
];


function searchForChildren(parentId, tree) {
  const children = [];
  tree.forEach(element => {
    if (element.parentUid === parentId) {
      children.push(element);
    }
  });
  for (const child of children) {
    const childrenTemp = searchForChildren(child.id, tree);
    children.push(...childrenTemp);
  }
  return children;
}

console.log(searchForChildren("2442092", data));
console.log(searchForChildren("2442086", data));

Из документов :

Метод concat () используется для объединения двух или более массивов. Этот метод не изменяет существующие массивы, но вместо этого возвращает новый массив.

0 голосов
/ 08 ноября 2018

Я бы создал индекс, чтобы уменьшить сложность поиска с O (n) до O (1). Для большого набора данных это будет иметь большое значение во времени выполнения. 

var index = {}, index_parent = {}, obj;
for (var i in myArray) {
  obj = myArray[i];
  index[obj.id] = obj;

  if (index_parent.hasOwnProperty(obj.parentUid)) {

    index_parent[obj.parentUid].push(obj.id);
  } else {
    index_parent[obj.parentUid] = [obj.id];
  }
}

, затем сделайте первый дыхательный поиск 

function getChildren_BFS (id_parent) {
  var out = [], qu = [], node, children;
  out.push(index[id_parent]); // this can be commented out if you don't need the root

  qu.push(id_parent);

  for (var current = 0; qu.length > current; ) {

    node = qu[current++];

    children = index_parent[node];

    if (children) {
      qu = qu.concat(children);

      children.forEach((e) => {out.push(index[e]);});
    }
  }

  return out;
}

var myArray = [{id: "7020441", parentUid: "2442074"}
,{id: "7020438", parentUid: "2442077"}
,{id: "7020435", parentUid: "2442079"}
,{id: "7020437", parentUid: "2442079"}
,{id: "7013749", parentUid: "2442086"}
,{id: "7013750", parentUid: "2442086"}
,{id: "7013752", parentUid: "2442086"}
,{id: "7013753", parentUid: "2442086"}
,{id: "7013751", parentUid: "2442086"}
,{id: "7013746", parentUid: "2442089"}
,{id: "7013747", parentUid: "2442089"}
,{id: "7013765", parentUid: "2442092"}
,{id: "7013767", parentUid: "2442092"}
,{id: "7013768", parentUid: "2442092"}
,{id: "2442074", parentUid: ""}
,{id: "2442075", parentUid: "2442074"}
,{id: "2442076", parentUid: "2442075"}
,{id: "2442077", parentUid: "2442076"}
,{id: "2442078", parentUid: "2442076"}
,{id: "2442079", parentUid: "2442075"}
,{id: "2442080", parentUid: "2442075"}
,{id: "2442081", parentUid: "2442075"}
,{id: "2442082", parentUid: "2442074"}
,{id: "2442083", parentUid: "2442074"}
,{id: "2442084", parentUid: "2442074"}
,{id: "2442085", parentUid: "2442084"}
,{id: "2442086", parentUid: "2442084"}
,{id: "2442087", parentUid: "2442084"}
,{id: "2442088", parentUid: "2442084"}
,{id: "2442089", parentUid: "2442088"}
,{id: "2442090", parentUid: "2442074"}
,{id: "2442092", parentUid: "2442091"}
,{id: "2442091", parentUid: "2442090"}
,{id: "2442093", parentUid: "2442090"}
,{id: "2442094", parentUid: "2442074"}
,{id: "2442095", parentUid: "2442074"}];

var index = {}, index_parent = {}, obj;
myArray.forEach((obj) => {

  index[obj.id] = obj;

  if (index_parent.hasOwnProperty(obj.parentUid)) {

    index_parent[obj.parentUid].push(obj.id);
  } else {
    index_parent[obj.parentUid] = [obj.id];
  }
});

console.log( getChildren_BFS("2442084") );
console.log( getChildren_BFS("2442074") );

Это необходимо улучшить на стороне памяти.

EDIT: Вот тот же самый getChildren, использующий поиск в глубину только путем изменения очереди для стека. 

function getChildren_DFS (id_parent) {
  var out = [], stack = [], node, children;
  out.push(index[id_parent]); // this can be commented out if you don't need the root

  stack.push(id_parent);

  while (stack.length > 0) {

    node = stack.pop();

    children = index_parent[node];

    if (children) {
      children.forEach((e) => {stack.push(e);});

      children.forEach((e) => {out.push(index[e]);});
    }
  }

  return out;
}
Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.

Нет похожих вопросов

...