javascript - 元素重复时如何将节点树合并为一棵

Question

我该如何解决必须合并具有重复值的树的情况？例如这样的：

  const firstTree = {
    id: 1,
    name: 'name1',
    otherProperty: 'property1',
    children: [
      {
        id: '1a',
        name: 'name1a',
        otherProperty: 'property1a',
        children: []
      },
      {
        id: '1b',
        name: 'name1b',
        otherProperty: 'property1b',
        children: [
          {
            id: '1ba',
            name: 'name1ba',
            otherProperty: 'property1ba',
            children: []
          },
          {
            id: '1bb',
            name: 'name1bb',
            otherProperty: 'property1bb',
            children: []
          }
        ]
      }
    ]
  };

  const secondTree = {
    id: 1,
    name: 'name1',
    otherProperty: 'property1',
    children: [
      {
        id: '1b',
        name: 'name1b',
        otherProperty: 'property1b',
        children: [
          {
            id: '1ba',
            name: 'name1ba',
            otherProperty: 'property1ba',
            children: []
          },
          {
            id: '2ba',
            name: 'name2ba',
            otherProperty: 'property2ba',
            children: []
          }
        ]
      }
    ]
  };

const thirdTree = {
  id: '3',
  name: 'name3',
  otherProperty: 'property3',
  children: [
    {
      id: '3a',
      name: 'name3a',
      otherProperty: 'property3a',
      children: []
    },
    {
      id: '3b',
      name: 'name3b',
      otherProperty: 'property3b',
      children: []
    }
  ]
};
const entryArray = [firstTree, secondTree, thirdTree];

因此，我希望将第一棵树与第二棵树合并，并将第三棵树合并，其中没有共同的元素：

const mergedFirstAndSecond = {
  id: 1,
  name: 'name1',
  otherProperty: 'property1',
  children: [
    {
      id: '1a',
      name: 'name1a',
      otherProperty: 'property1a',
      children: []
    },
    {
      id: '1b',
      name: 'name1b',
      otherProperty: 'property1b',
      children: [
        {
          id: '1ba',
          name: 'name1ba',
          otherProperty: 'property1ba',
          children: []
        },
        {
          id: '1bb',
          name: 'name1bb',
          otherProperty: 'property1bb',
          children: []
        },
        {
          id: '2ba',
          name: 'name2ba',
          otherProperty: 'property2ba',
          children: []
        }
      ]
    }
  ]
};
const result = [mergedFirstAndSecond, thirdTree];

我的意思是，如果重复元素也出现在三个不同的树中，而不仅仅是两个，那么这个解决方案也可以工作。我将非常感谢任何建议。

标签： javascriptrecursiontreenodes

Answer 1

您可以使用递归来合并它们ids 上的树：

var firstTree = {'id': 1, 'name': 'name1', 'otherProperty': 'property1', 'children': [{'id': '1a', 'name': 'name1a', 'otherProperty': 'property1a', 'children': []}, {'id': '1b', 'name': 'name1b', 'otherProperty': 'property1b', 'children': [{'id': '1ba', 'name': 'name1ba', 'otherProperty': 'property1ba', 'children': []}, {'id': '1bb', 'name': 'name1bb', 'otherProperty': 'property1bb', 'children': []}]}]};
var secondTree = {'id': 1, 'name': 'name1', 'otherProperty': 'property1', 'children': [{'id': '1b', 'name': 'name1b', 'otherProperty': 'property1b', 'children': [{'id': '1ba', 'name': 'name1ba', 'otherProperty': 'property1ba', 'children': []}, {'id': '2ba', 'name': 'name2ba', 'otherProperty': 'property2ba', 'children': []}]}]};
var thirdTree = {'id': '3', 'name': 'name3', 'otherProperty': 'property3', 'children': [{'id': '3a', 'name': 'name3a', 'otherProperty': 'property3a', 'children': []}, {'id': '3b', 'name': 'name3b', 'otherProperty': 'property3b', 'children': []}]};
var entryArray = [firstTree, secondTree, thirdTree];
function merge_trees(trees){
   var merger = {};
   //find matches based on id
   for (var t of trees){
      for (var i of t){
        if (!(i['id'] in merger)){
           merger[i['id']] = Object.fromEntries(Object.keys(i).map(x => [x, (new Set([i[x]]))]));
        }
        for (var k of Object.keys(i)){
           merger[i['id']][k] = new Set([...(k in merger[i['id']] ? merger[i['id']][k] : []), i[k]]);
        }
      }
   }
   var new_result = [];
   //iterate over merges
   for (var i of Object.keys(merger)){
      var result = {}
      for (var k of Object.keys(merger[i])){
         //choose whether or not to merge again based on the size of the merged children
         if (k === 'children'){
            result[k] = merger[i][k].size > 1 ? merge_trees(merger[i][k]) : [...merger[i][k]].filter(x => x.length > 1)
         }
         else{
             result[k] = merger[i][k].size === 1 ? [...merger[i][k]][0] : [...merger[i][k]] 
         }
      }
      new_result.push(result)
   }
   return new_result;
}
console.log(merge_trees(entryArray.map(x => [x])))