将按 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 之间的数字。请注意，代码来自服务器，在 [=13 旁边会有一些额外的属性=] 喜欢 title 但在这个问题上并不重要。

这里的主要思想是为 jsTree.

制作一个合适的格式

Answer 1

您可以使用递归解决方案来做到这一点。这个想法是维护 path （通过 String.prototype.match 和正则表达式作为数组获得）和 parent ，你想为每个递归调用插入 code 。

parent 跟踪您要在 "current" 递归调用中选择的节点，并且 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被插入时，它的父节点已经被插入了。

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

为了编写构建所需结构的递归函数，我付出了很多努力。找到答案 here

但要做到这一点，您必须先将 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

代码有点长，但在我看来很容易理解。它非常健壮——不需要对数组进行排序，也不需要存在 01 来处理 0102（以防万一）。如果不处理这些情况，代码可以更短，但我认为您可能需要这个。

首先，从数据中创建一个基于对象的树数据结构。这棵树有键和值，并且构建起来非常高效，因为通过索引访问是 O(1)。接下来，通过遍历object-based tree，然后将每一层转化为数组，将object-based tree转化为最终的array-based tree数据结构。

我也大量使用递归，因为递归非常适合创建和遍历树。

与其他答案相比，我的算法具有更好的时间复杂度，因为我在创建树时创建了一个具有 O(1) 访问权限的 dictionary/object。其他算法在每一层内进行搜索，效率低下。我的算法运行s 在 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));

将按 ASCII 顺序排序的一维数组转换为 Javascript 中的嵌套数组

Convert 1D array sorted by ASCII order to a nested array in Javascript

javascript

arrays

jstree