JavaScript：四叉树比较

Question

我没有找到任何快速算法来获取以下格式的四叉树差异。假设我们有两个任意的 4 级树：

var tree1 = [

    { id: "1.1", children: [

        { id: "1.1.1", children: null },
        { id: "1.1.2", children: null },
        { id: "1.1.3", children: [

            { id: "1.1.3.1", children: null },
            { id: "1.1.3.2", children: null },
            { id: "1.1.3.3", children: null },
            { id: "1.1.3.4", children: null }

        ] },
        { id: "1.1.4", children: null }

    ] },
    { id: "1.2", children: null },
    { id: "1.3", children: [

        { id: "1.3.1", children: [

            { id: "1.3.1.1", children: null },
            { id: "1.3.1.2", children: null },
            { id: "1.3.1.3", children: null },
            { id: "1.3.1.4", children: null }

        ] },
        { id: "1.3.2", children: null },
        { id: "1.3.3", children: null },
        { id: "1.3.4", children: null }

    ] },
    { id: "1.4", children: null }

];

var tree2 = [

  { id: "1.1", children: [

        { id: "1.1.1", children: null },
        { id: "1.1.2", children: null },
        { id: "1.1.3", children: null },
        { id: "1.1.4", children: [

            { id: "1.1.4.1", children: null },
            { id: "1.1.4.2", children: null },
            { id: "1.1.4.3", children: null },
            { id: "1.1.4.4", children: null }

        ] }

  ] },
  { id: "1.2", children: [

        { id: "1.2.1", children: null },
        { id: "1.2.2", children: null },
        { id: "1.2.3", children: [

            { id: "1.2.3.1", children: null },
            { id: "1.2.3.2", children: null },
            { id: "1.2.3.3", children: null },
            { id: "1.2.3.4", children: null }

        ] },
        { id: "1.2.1", children: null }

  ]},
  { id: "1.3", children: null },
  { id: "1.4", children: [

        { id: "1.4.1", children: [

            { id: "1.4.1.1", children: null },
            { id: "1.4.1.2", children: null },
            { id: "1.4.1.3", children: null },
            { id: "1.4.1.4", children: null }

        ] },
        { id: "1.4.2", children: null },
        { id: "1.4.3", children: null },
        { id: "1.4.1", children: null }

  ] }

];

所以，我需要找出不同点，return 它们是：

var result = {

    "1.1.3.1" : "1.1.3",
    "1.1.3.2" : "1.1.3",
    "1.1.3.3" : "1.1.3",
    "1.1.3.4" : "1.1.3",
    "1.1.4" : ["1.1.4.1", "1.1.4.2", "1.1.4.3", "1.1.4.4"],
    "1.2" : ["1.2.1", "1.2.2". ["1.2.3.1", "1.2.3.2", "1.2.3.3", "1.2.3.4"], "1.2.4"],
    "1.3.1.1" : "1.3",
    "1.3.1.2" : "1.3",
    "1.3.1.3" : "1.3",
    "1.3.1.4" : "1.3",
    "1.3.2" : "1.3",
    "1.3.3" : "1.3",
    "1.3.4" : "1.3",
    "1.4" : [["1.4.1.1", "1.4.1.2", "1.4.1.3", "1.4.1.4"], "1.4.2", "1.4.3", "1.4.4"]

 };

如果你能看到，结果必须是与更新对应的地图或字典。不知道如何将 ["1.1.3.1", "1.1.3.2", "1.1.3.3", "1.1.3.4"] 引用到单个索引，所以我将它们分开，但是如果有更优雅的好的，不客气。

此数据为人工制作，如有错误请见谅。

Answer 1

您可以构建一棵树，在其中为树的 adding/deleting 部分添加标记 where，然后从中得出差异。

function getDifference(t1, t2) {

    function getD(object, parent) {
        function getKeys({ where, ...object }) {
            return Object.keys(object).flatMap(k => [k, ...(object[k] ? getKeys(object[k]) : [])]);
        }

        var types;

        Object
            .entries(object)
            .forEach(([k, { where, ...o }]) => {
                if (where) {
                    let keys = getKeys(o);
                    if (!types) types = {};
                    if (!types[where]) types[where] = [];
                    types[where].push(keys.length ? [k, keys] : k);
                } else {
                    getD(o, k);
                }
            });

        if (types) {
            if (-1 in types) result.push([types[-1], parent]);
            if (1 in types) result.push([parent, types[1]]);
        }
    }

    var temp = {},
        add = (inc, tree) => ({ id, children }) => {
            tree[id] = tree[id] || { where: 0 };
            tree[id].where += inc;
            if (children) children.forEach(add(inc, tree[id]));
        },
        result = [];

    t1.forEach(add(-1, temp));
    t2.forEach(add(1, temp));

    getD(temp);

    return result;
}    

var tree1 = [{ id: "1.1", children: [{ id: "1.1.1", children: null }, { id: "1.1.2", children: null }, { id: "1.1.3", children: [{ id: "1.1.3.1", children: null }, { id: "1.1.3.2", children: null }, { id: "1.1.3.3", children: null }, { id: "1.1.3.4", children: null }] }, { id: "1.1.4", children: null }] }, { id: "1.2", children: null }, { id: "1.3", children: [{ id: "1.3.1", children: [{ id: "1.3.1.1", children: null }, { id: "1.3.1.2", children: null }, { id: "1.3.1.3", children: null }, { id: "1.3.1.4", children: null }] }, { id: "1.3.2", children: null }, { id: "1.3.3", children: null }, { id: "1.3.4", children: null }] }, { id: "1.4", children: null }],
    tree2 = [{ id: "1.1", children: [{ id: "1.1.1", children: null }, { id: "1.1.2", children: null }, { id: "1.1.3", children: null }, { id: "1.1.4", children: [{ id: "1.1.4.1", children: null }, { id: "1.1.4.2", children: null }, { id: "1.1.4.3", children: null }, { id: "1.1.4.4", children: null }] }] }, { id: "1.2", children: [{ id: "1.2.1", children: null }, { id: "1.2.2", children: null }, { id: "1.2.3", children: [{ id: "1.2.3.1", children: null }, { id: "1.2.3.2", children: null }, { id: "1.2.3.3", children: null }, { id: "1.2.3.4", children: null }] }, { id: "1.2.4", children: null }] }, { id: "1.3", children: null }, { id: "1.4", children: [{ id: "1.4.1", children: [{ id: "1.4.1.1", children: null }, { id: "1.4.1.2", children: null }, { id: "1.4.1.3", children: null }, { id: "1.4.1.4", children: null }] }, { id: "1.4.2", children: null }, { id: "1.4.3", children: null }, { id: "1.4.4", children: null }] }],
    result = getDifference(tree1, tree2);

console.log(result);

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

JavaScript：四叉树比较

JavaScript: Quadtree comparison

javascript

tree

search

quadtree

difference