Конвертировать массив 1D, отсортированный по ASCII-порядку, во вложенный массив в Javascript

Question

Предположим, что ниже приведен массив объектов, отсортированных по свойству code в порядке ascii:

var codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

Как я могу преобразовать его во вложенный массив, например:

var nestedCodes = [
    {
        code: '01',
        children: [
            { code: '0101' },
            {
                code: '0102',
                children: [
                    { code: '010201' }
                ]
            },
            { code: '0103' }
        ]
    },
    {
        code: '02',
        children: [
            { code: '0201' },
            { code: '0202' }
        ]
    }
];

Структура кодов похожа на конкатенацию нескольких 0N, что N может быть числом от 1 до 9. Обратите внимание, что коды поступают с сервера, и помимо code будут некоторые дополнительные свойства, такие как title, но это не так.вопрос в этой проблеме.

Основная идея здесь - создать соответствующий формат для jsTree .

Answer 1

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

Во-первых, создайте объектную древовидную структуру данных из данных.Это дерево имеет ключи и значения и очень эффективно для построения, потому что доступ по индексу - O (1).Затем преобразуйте объектное дерево в окончательную структуру данных на основе массива, обойдя объектное дерево и затем преобразовав каждый слой в массивы.

Я также активно использую рекурсию, поскольку рекурсия хорошо подходитдля создания и обхода деревьев.

По сравнению с другими ответами мой алгоритм имеет большую временную сложность, потому что я создаю словарь / объект, который имеет O (1) доступ при создании дерева.Другие алгоритмы выполняют поиск в каждом слое, что неэффективно.Мой алгоритм работает в O (N), тогда как другие ответы здесь короче, но в O (N ^ 2).

Просто скопируйте функцию format в ваш код, и она должна быть полезной.

const codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

function format(codes) {
  // Splits the string into an array of 2-character strings.
  const SPLIT_REGEX = /.{2}(?=(.{2})+(?!.))|.{2}$/g;
  const codeFragments = codes.map(obj => obj.code.match(SPLIT_REGEX));

  // 1. Represent the data as a tree which is more efficient to build.
  const tree = {};
  function createTree(tree, fragments) {
    let node = tree;
    fragments.forEach(fragment => {
      if (!node[fragment]) {
        node[fragment] = {};
      }
      node = node[fragment];
    });
  }
  codeFragments.forEach(fragments => createTree(tree, fragments));
  /* tree will have the structure:
  {
    "01": {
      "01": {},
      "02": {
        "01": {}
      },
      "03": {}
    },
    "02": {
      "01": {},
      "02": {}
    }
  }
  */

  // 2. Convert the tree structure into the desired format.
  function generateCodesFromTree(tree, previous) {
    const nestedCodes = [];
    Object.keys(tree).forEach(treeNode => {
      const code = previous + treeNode;
      const children = generateCodesFromTree(tree[treeNode], code);
      const nestedCode = { code };
      if (children.length > 0) {
        nestedCode.children = children;
      }
      nestedCodes.push(nestedCode);
    });
    return nestedCodes;
  }

  return generateCodesFromTree(tree, '');
}

console.log(format(codes));

Answer 2

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

let codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

roots = codes.filter(c => c.code.length === 2);

roots.forEach(c => assign(c));

console.log(roots);

function assign(code) {
  codes.forEach(c => {
    if (c !== code) {
      if (code.code === c.code.slice(0, code.code.length)) {
        code.children = !code.children ? [c] : [...code.children, c];
        assign(code.children[code.children.length - 1]);
      }
    }
  });
}

Answer 3

Я изо всех сил пытался написать рекурсивную функцию, которая создаст необходимую структуру.Нашел ответ здесь

Но для этого нужно сначала добавить свойство parent к каждому массиву codes.Я сделал это в предположении, что у каждого code есть родительский элемент, который эквивалентен самому коду, за исключением двух последних байтов.

var codes = [{code: '01'    },
             {code: '0101'  },
             {code: '0102'  },
             {code: '010201'},
             {code: '0103'  },
             {code: '02'    },
             {code: '0201'  },
             {code: '0202'  },
          ];

// add parents to each code
codes.forEach(function(c) {
  if (c.code.length > 2) {
    c.parent = c.code.substr(0, c.code.length - 2);
  } else {
    c.parent = 'root';
  }
});



function find_children(arr, parent) {
  var out = [];
  for (var i in arr) {
    
    if (arr[i].parent == parent) {
      
      var children = find_children(arr, arr[i].code);

      if (children.length) {
        arr[i].children = children;
      }
      out.push(arr[i])
    }
  }
  return out;
}

var nested = find_children(codes,'root');
console.log(nested);

Answer 4

Вы можете сделать это с помощью рекурсивного решения.Идея состоит в том, чтобы сохранить path (полученный в виде массива через String.prototype.match с регулярным выражением) и parent, в который вы хотите вставить code для каждого рекурсивного вызова.

parent отслеживает узел, который вы хотите выбрать в "текущем" рекурсивном вызове, и path помогает в построении parent, поскольку вы продолжаете идти глубже:

function insert(d, path, parent, arr) {
  if (path.length === 0) {
    arr.push(Object.assign({}, d));
    return;
  }
  var target = arr.find(e => e.code === parent);
  target.children = target.children || [];
  insert(d, path.slice(1), parent + path[0], target.children);
}

var codes = [
    { code: '01' },
    { code: '0101' },
    { code: '0102' },
    { code: '010201' },
    { code: '0103' },
    { code: '02' },
    { code: '0201' },
    { code: '0202' },
];

var res = codes.reduce((a, c) => {
  var p = c.code.match(/(0[1-9])/g);
  insert(c, p.slice(1), p[0], a);
  return a;
}, []);

console.log(res);

Предполагается, конечно, что при вставке code его родительский элемент уже был вставлен ранее.