合并两棵树仅将唯一节点从一棵树添加到下一棵树

Question

我正在尝试将 Tree2 合并到 Tree1 中。合并结果包含 Tree1 中的所有现有节点以及 Tree2 节点，这些节点位于层次结构中的正确级别，这些节点在 Tree1 中不存在。最终的树输入更大更深，但我一直在努力处理下面的简单示例树。

Tree1 = {"name":"A","children":[{"name":"B","children":[{"name":"C","children":[]}]},"name":"B1","children":[{"name":"C1","children":[]}]}]}
Tree2 = {"name":"A", "children":[{"name":"B", "children":[{"name":"C2", "children":[]}]}]}

merged = {"name":"A","children":[{"name":"B","children":[{"name":"C","children":[]},{"name":"C2","children":[]}]},{"name":"B1","children":[{"name":"C1","children":[]}]}]}

Answer 1

可以通过查看同级别的名字属性来合并

这种方法returns一个数组，因为如果你对根有不同的名字，结果至少包含两个对象。

const
    merge = (a, b) => {
        if (!Array.isArray(a)) a = [a];
        if (!Array.isArray(b)) b = [b];
        return [...a, ...b].reduce((r, o) => {
            const item = r.find(({ name }) => o.name === name);
            if (item) item.children = merge(item.children, o.children);
            else r.push(o);
            return r;
        }, []);
    },
    tree1 = { name: "A", children: [{ name: "B", children: [{ name: "C", children: [] }] }, { name: "B1", children: [{ name: "C1", children: [] }] }] },
    tree2 = { name: "A", children: [{ name: "B", children: [{ name: "C2", children: [] }] }] },
    result = merge(tree1, tree2);

console.log(result);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 2

您可以使用递归来合并您的树：

function merge(...trees){
   var m = {};
   for (var i of trees){
      m[i.name] = [...(i.name in m ? m[i.name] : []), ...i.children];
   }
   return Object.keys(m).map(function(x){return {name:x, children:m[x].length > 1 ? merge(...m[x]) : m[x]}})
}

Answer 3

我们注意到 children 的收集列表与我们函数的初始参数的相似性，并且可以以简单的递归结束。在这里，我们将树折叠成 object，其键是 name，其值是收集到的 children。然后我们调用 Object .entries 并将 key-value 对映射到 name 和（通过递归调用）每个的 children 属性。仅此而已

const mergeTrees = (...trees) => 
  Object .entries (trees .reduce ((a, {name, children = []}) => ({
    ...a, 
    [name]: (a [name] || []) .concat (children)
  }), {})) .map (([k, v]) => ({name: k, children : mergeTrees (...v)}))

const tree1 = {name: "A", children: [{name: "B", children: [{name: "C", children: []}]}, {name: "B1", children: [{name: "C1", children: []}]}]}
const tree2 = {name: "A", children: [{name: "B", children: [{name: "C2", children: []}]}]}

console .log (mergeTrees (tree1, tree2))

.as-console-wrapper {max-height: 100% !important; top: 0}

请注意，我们 return 是一片森林，而不是一棵树。如果你知道所有的树都有相同的根，那么你可以从结果中提取第一个元素。

合并两棵树仅将唯一节点从一棵树添加到下一棵树

merge two trees adding only unique nodes from one tree to the next

javascript

tree

recursion

merge

json