js解决JSON子节点转根节点,使用深度优先遍历算法已实现(d3.js树状关系网络)

Question

有如下一段json数据

{
    "name": "18912386146", 
    "size": 45, 
    "children": [
        {
            "name": "13811179796", 
            "size": 10
        }, 
        {
            "name": "18511331067", 
            "size": 10
        }, 
        {
            "name": "18631867507", 
            "size": 10
        }, 
        {
            "name": "18616261983", 
            "size": 45, 
            "children": [
                {
                    "name": "13811179796", 
                    "size": 10
                }, 
                {
                    "name": "18995390312", 
                    "size": 10
                }
            ]
        }, 
        {
            "name": "13466692515", 
            "size": 10
        }, 
        {
            "name": "13650731515", 
            "size": 45, 
            "children": [
                {
                    "name": "13811179796", 
                    "size": 10
                }, 
                {
                    "name": "13037986580", 
                    "size": 10
                }, 
                {
                    "name": "18995390312", 
                    "size": 10
                }
            ]
        }, 
        {
            "name": "15809619551", 
            "size": 10
        }, 
        {
            "name": "18601191669", 
            "size": 10
        }, 
        {
            "name": "15909638715", 
            "size": 10
        }, 
        {
            "name": "15909619055", 
            "size": 10
        }, 
        {
            "name": "18902266418", 
            "size": 63, 
            "children": [
                {
                    "name": "13560047280", 
                    "size": 63
                },
                {
                    "name": "13632270695", 
                    "size": 10
                }, 
                {
                    "name": "13650731515", 
                    "size": 45
                }, 
                {
                    "name": "13268069280", 
                    "size": 167
                }
            ]
        }, 
        {
            "name": "13037986580", 
            "size": 10
        }, 
        {
            "name": "18995390312", 
            "size": 10
        }
    ]
}

上面这段json数据对应成图,
现在点击紫色的大圆点,即其中一个叶子节点,会反转成根节点,重新生成图形,这样一个效果;
只需要对json数据进行反转即可;
需要通过遍历算法转成下面这样

{
    "name": "13268069280", 
    "size": 167, 
    "children": [
        {
            "name": "18902266418", 
            "size": 63,
            "children": [
                {
                    "name": "13560047280", 
                    "size": 63
                },
                {
                    "name": "13632270695", 
                    "size": 10
                }, 
                {
                    "name": "13650731515", 
                    "size": 45
                }, 
                {
                    "name": "18912386146", 
                    "size": 45,
                    "children": [
                        {
                            "name": "13811179796", 
                            "size": 10
                        }, 
                        {
                            "name": "18511331067", 
                            "size": 10
                        }, 
                        {
                            "name": "18631867507", 
                            "size": 10
                        }, 
                        {
                            "name": "18616261983", 
                            "size": 45, 
                            "children": [
                                {
                                    "name": "13811179796", 
                                    "size": 10
                                }, 
                                {
                                    "name": "18995390312", 
                                    "size": 10
                                }
                            ]
                        }, 
                        {
                            "name": "13466692515", 
                            "size": 10
                        }, 
                        {
                            "name": "13650731515", 
                            "size": 45, 
                            "children": [
                                {
                                    "name": "13811179796", 
                                    "size": 10
                                }, 
                                {
                                    "name": "13037986580", 
                                    "size": 10
                                }, 
                                {
                                    "name": "18995390312", 
                                    "size": 10
                                }
                            ]
                        }, 
                        {
                            "name": "15809619551", 
                            "size": 10
                        }, 
                        {
                            "name": "18601191669", 
                            "size": 10
                        }, 
                        {
                            "name": "15909638715", 
                            "size": 10
                        }, 
                        {
                            "name": "15909619055", 
                            "size": 10
                        }, 
                        {
                            "name": "13037986580", 
                            "size": 10
                        }, 
                        {
                            "name": "18995390312", 
                            "size": 10
                        }
                    ]
                }
            ]
        }
    ]
}

不知道各位有没有比较好的算法实现,我已实现一个版本

上下2段json对应成d3关系图分别是

Answer 1

function plainJSON(root, node, queue, level) {
    var nodeIndex = -1;

    queue.push({
        level: level,
        self: root
    });
    if (!!root.children) {
        root.children.map((child) => {
            const i = plainJSON(child, node, queue, level + 1);
            if (i >= 0) nodeIndex = i;
        })
    }
    if (root === node) {
        nodeIndex = queue.length - 1;
    }
    return nodeIndex;
}

function removeChildren(parent, child) {
    if (!parent.children) return -1;
    const index = parent.children.indexOf(child);
    (index >= 0) && parent.children.splice(index, 1);
    return index;
}

function isArray(o) {  
  return Object.prototype.toString.call(o) === '[object Array]';   
} 

function dfs(_key,o){
    if(o.name && _key == o.name) return o;
    if(o.children) { 
        for (var v in o.children) {
          var r = dfs(_key,o.children[v]);
          if(r) return r;
      }
    } 
}

function revertTree(data, node) {
    const queue = [];
    const qIndex = plainJSON(data, node, queue, 0);
    if (qIndex < 0) return null;

    const keyNodeLevel = queue[qIndex].level;

    var levelCursor = keyNodeLevel - 1;
    var nodePath = [qIndex];

    for (var i = qIndex - 1; i >= 0; i--) {
        if (queue[i].level === levelCursor) {
            levelCursor--;
            nodePath.push(i);
        }
    }
    for (var i = 0, until = nodePath.length - 1; i < until; i++) {
        var parent = queue[nodePath[i + 1]].self,
              child = queue[nodePath[i]].self;
        removeChildren(parent, child);
        child.children = child.children || [];
        child.children.push(parent);
    }
    return queue[qIndex].self;
}

function revert(data, key) {
    return revertTree(data,dfs(key,data));
}

测试

var data = {
    "name": "18912386146", 
    "size": 45, 
    "children": [
        {
            "name": "13811179796", 
            "size": 10
        }, 
        {
            "name": "18511331067", 
            "size": 10
        }, 
        {
            "name": "18631867507", 
            "size": 10
        }, 
        {
            "name": "18616261983", 
            "size": 45, 
            "children": [
                {
                    "name": "13811179796", 
                    "size": 10
                }, 
                {
                    "name": "18995390312", 
                    "size": 10
                }
            ]
        }, 
        {
            "name": "13466692515", 
            "size": 10
        }, 
        {
            "name": "13650731515", 
            "size": 45, 
            "children": [
                {
                    "name": "13811179796", 
                    "size": 10
                }, 
                {
                    "name": "13037986580", 
                    "size": 10
                }, 
                {
                    "name": "18995390312", 
                    "size": 10
                }
            ]
        }, 
        {
            "name": "15809619551", 
            "size": 10
        }, 
        {
            "name": "18601191669", 
            "size": 10
        }, 
        {
            "name": "15909638715", 
            "size": 10
        }, 
        {
            "name": "15909619055", 
            "size": 10
        }, 
        {
            "name": "18902266418", 
            "size": 63, 
            "children": [
                {
                    "name": "13560047280", 
                    "size": 63
                },
                {
                    "name": "13632270695", 
                    "size": 10
                }, 
                {
                    "name": "13650731515", 
                    "size": 45
                }, 
                {
                    "name": "13268069280", 
                    "size": 167
                }
            ]
        }, 
        {
            "name": "13037986580", 
            "size": 10
        }, 
        {
            "name": "18995390312", 
            "size": 10
        }
    ]
}

function cloneData () {
    return JSON.parse(JSON.stringify(data));
}

var dataCopy1 = cloneData();

console.log(
    JSON.stringify(revert(dataCopy1, "13268069280"), null, 4)
);

搞定收工!