如何合并多维数组。

Question

var list1 = [
    {
        id: 'node1',
        children: [
            {
                id: 'node11',
                children: []
            }
        ]
    }
];

var list2 = [
    {
        id: 'node1',
        children: [
            {
                id: 'node13',
                children: []
            }
        ]
    }
];
var resultList = [
    {
        id: 'node1',
        children: [
            {
                id: 'node11',
                children: []
            }, {
                id: 'node13',
                children: []
            }
        ]
    }
];

我所有的数组都是树形结构，一个节点只能属于一个父节点。

我想将list1和list2合并，得到resultList。我尝试了多种方法，包括递归回调、字符串搜索和替换等，但仍然无法解决问题。

- Aflext

Answer 1

如果我理解正确的话，您希望通过id将其压缩。

function getCompactById(arr) { // must have the same id
    var res = [];
    var obj = {};
    obj.id = arr[0][0].id;
    obj.children = [];
    for(var i = 0; i < arr.length; i += 1) {
        obj.children.push(arr[i][0].children[0]);
    }
    res.push(obj);
    return res;
}

数组看起来像 var arr = [list1, list2]; 在函数create中创建一个数组和一个对象。对象获得一个id和一个数组。id始终相同，因此我们从第一个数组中获取它。 遍历数组并将所有对象arr[i][0].children[0]推入其中。 循环后将obj推入数组中。 返回结果数组。

演示

- user3589620

---

然而，这并不会递归地合并整个树。它只在第一级上合并，之后的所有内容都只是被复制。 - TimoStaudinger

Answer 2

以下代码将合并两个树形数组的所有层级，而不仅仅是最上层的层级：

var list1 = ...
var list2 = ...

var addNode = function(nodeId, array) {
  array.push({id: nodeId, children: []});
};

var placeNodeInTree = function(nodeId, parent, treeList) {
  return treeList.some(function(currentNode){

    // If currentNode has the same id as the node we want to insert, good! Required for root nodes.
    if(currentNode.id === nodeId) {
      return true;  
    }

    // Is currentNode the parent of the node we want to insert?
    if(currentNode.id === parent) {

      // If the element does not exist as child of currentNode, create it
      if(!currentNode.children.some(function(currentChild) {
        return currentChild.id === nodeId;
      })) addNode(nodeId, currentNode.children);

      return true;
    } else {

      // Continue looking further down the tree
      return placeNodeInTree(nodeId, parent, currentNode.children);
    }
  });
};

var mergeInto = function(tree, mergeTarget, parentId) {
  parentId = parentId || undefined;
  tree.forEach(function(node) {

    // If parent has not been found, placeNodeInTree() returns false --> insert as root element
    if(!placeNodeInTree(node.id, parentId, mergeTarget)){
      list1.push({id: node.id, children:[]});
    }

    mergeInto(node.children, mergeTarget, node.id);

  });
};

mergeInto(list2, list1);

document.write('<pre>');
document.write(JSON.stringify(list1, null, 4));
document.write('</pre>');

在JSBin上查看代码实现：http://jsbin.com/wikaricita/3/edit?js,output

请注意，该算法的复杂度为O(n^2)，这意味着它不会很好地扩展。如果树变得非常大或性能是一个关键问题，您可能需要考虑其他解决此问题的方法。

- TimoStaudinger

---

列表3是预期结果。 - Aflext

你的数组是树形结构吗？还是一个元素可以有多个父节点？如果它应该是一棵树，那么当你想要合并两个数组之间存在冲突的定义时，你希望如何处理？ - TimoStaudinger

是的，这两个数组是树形结构。我的目标是将从服务器获取的新的树形结构合并到现有的DOM内存树形结构数组中，就像“更新已显示的树形结构”一样。 - Aflext