tree树节点合并

Question

// 数据
const obj1 = [
   {
      name: 'code',
      child: [
         {
            name: 'solution',
            child: [
               {
                 name: 'base',
                 child: [
                    name: 'tool',
                     child: []
                  ]
               }
            ]
         }
      ]
   }
]
const obj2 = [
   {
      name: 'code',
      child: [
         {
            name: 'solution',
            child: [
               {
                 name: 'algorithm',
                 child: [
                    name: 'list',
                     child: []
                  ]
               }
            ]
         }
      ]
   }
]

想合并成

const obj3 = [
   {
      name: 'code',
      child: [
         {
            name: 'solution',
            child: [
               {
                 name: 'base',
                 child: [
                    name: 'tool',
                     child: []
                  ]
               },
               {
                 name: 'algorithm',
                 child: [
                    name: 'list',
                     child: []
                  ]
               }
            ]
         }
      ]
   }
]

const isSame = (target, source) => {
  console.log(target, source)
  if (target[0].children.length && source[0].children.length) {
    return
  }
  for (let i = 0; i < source.length; i++) {
    if (source[i].children.length) {
      if (source[i].children[0].children.length === 0) {
        if (source[i].name === target[i].name) {
          target[i].children.push(...source[i].children)
        }
      }
      isSame(target[i].children, source[i].children)
    }
  }
}
一开始想遍历对比每个节点，但是发现效果走不下去

Answer 1

const obj1 = [
  {
    name: 'code',
    child: [
      {
        name: 'solution',
        child: [
          {
            name: 'base',
            child: [{ name: 'tool', child: [] }],
          },
        ],
      },
    ],
  },
]
const obj2 = [
  {
    name: 'code',
    child: [
      {
        name: 'solution',
        child: [
          {
            name: 'algorithm',
            child: [{ name: 'list', child: [] }],
          },
        ],
      },
    ],
  },
  {
    name: 'ccc',
    child: [],
  },
]

/**
 * 将数组类型的child转换为map类型，以实现O(n)时间复杂度的合并
 * @param {要进行转换的数据} data
 */
const generateMapTreeData = (data) => {
  const dummyRoot = {
    name: 'dummyRoot',
    children: {},
  }

  const dfs = (vertex, origin) => {
    if (!origin.children) origin.children = {}
    origin.children[vertex.name] = vertex

    for (let i = 0; i < vertex.child.length; ++i) {
      dfs(vertex.child[i], vertex)
    }
  }

  for (let i = 0; i < data.length; ++i) {
    dfs(data[i], dummyRoot)
  }

  return dummyRoot
}

/**
 * 将map类型的treeData转换为数组类型的
 * @param {要转换的数据} data
 */
const generateArrayTreeData = (data) => {
  const dfs = (vertex, origin) => {
    if (!vertex.children) return

    const keys = Object.keys(vertex.children)

    for (const key of keys) {
      const newVertex = {
        name: key,
        child: [],
      }
      origin.child.push(newVertex)
      dfs(vertex.children[key], newVertex)
    }
  }

  const ans = []

  const keys = Object.keys(data.children)

  for (const key of keys) {
    const vertex = {
      name: key,
      child: [],
    }

    dfs(data.children[key], vertex)
    ans.push(vertex)
  }

  return ans
}

/**
 * 更具key合并两个对象
 * @param {*} obj1
 * @param {*} obj2
 */
const merge = (obj1, obj2) => {
  obj1 = generateMapTreeData(obj1)
  obj2 = generateMapTreeData(obj2)

  const ans = {
    name: 'dummyRoot',
    children: {},
  }

  const dfs = (obj1, obj2, ans) => {
    if (!ans.children) ans.children = {}
    if (!obj1) {
      ans.children = obj2.children || {}
      return
    }

    if (!obj2) {
      ans.children = obj1.children || {}
      return
    }

    const keys = [...Object.keys(obj1.children), ...Object.keys(obj2.children)]

    for (const key of keys) {
      ans.children[key] = { ...obj1.children[key], ...obj2.children[key] }
      dfs(obj1.children[key], obj2.children[key], ans.children[key])
    }
  }

  dfs(obj1, obj2, ans)

  return generateArrayTreeData(ans)
}

console.log(JSON.stringify(merge(obj1, obj2), null, 2))

Answer 2

function merge(target, source) {
    target.forEach((v,i) => {
        if(v.name == source[i].name) merge(v.child, source[i].child)
        else target.push(source[i])
    })
    return target;
}

已参与了 SegmentFault 思否「问答」打卡，欢迎正在阅读的你也加入

Answer 3

/**
 * 合并两个数组，根据元素的 name 判断是否合并子其子数组。
 * @param {Array} target 即是源，也是合并的结果
 * @param {Array} source 另一个源
 */
function merge(target = [], source = []) {
    // 先建个表，方便查找
    const dict = Object.fromEntries(target.map(it => [it.name, it]));
    
    source.forEach(s => {
        const t = dict[s.name];
        if (t) {
            t.child = merge(t.child, s.child);
        } else {
            target.push(s);
        }
    });
    return target;
}

---

已参与了 SegmentFault 思否「问答」打卡，欢迎正在阅读的你也加入。