「NodeJS,全栈全端」js 解决 JSON 子节点转根节点,本人使用深度优先遍历算法未实现(d3.js 树状关系网络),求一段优雅的 js

需求抽象一下吧,

输入json为

{"name":"A","size":45,"children":[{"name":"B","size":10},{"name":"C","size":10},{"name":"D","size":10},{"name":"E","size":45,"children":[{"name":"B","size":10},{"name":"F","size":10}]},{"name":"G","size":10},{"name":"H","size":45,"children":[{"name":"B","size":10},{"name":"I","size":10},{"name":"F","size":10}]},{"name":"J","size":10},{"name":"Q","size":10},{"name":"L","size":10},{"name":"M","size":10},{"name":"N","size":63,"children":[{"name":"O","size":63},{"name":"P","size":10},{"name":"H","size":45},{"name":"Q","size":167}]},{"name":"I","size":10},{"name":"R","size":10}]}

对应成图 enter image description here

输出json为 { "name": "Q", "size": 167, "children": [ { "name": "N", "size": 63, "children": [ { "name": "O", "size": 63 }, { "name": "P", "size": 10 }, { "name": "H", "size": 45 }, { "name": "A", "size": 45, "children": [ { "name": "B", "size": 10 }, { "name": "C", "size": 10 }, { "name": "D", "size": 10 }, { "name": "E", "size": 45, "children": [ { "name": "B", "size": 10 }, { "name": "F", "size": 10 } ] }, { "name": "G", "size": 10 }, { "name": "H", "size": 45, "children": [ { "name": "B", "size": 10 }, { "name": "I", "size": 10 }, { "name": "F", "size": 10 } ] }, { "name": "J", "size": 10 }, { "name": "Q", "size": 10 }, { "name": "L", "size": 10 }, { "name": "M", "size": 10 }, { "name": "I", "size": 10 }, { "name": "R", "size": 10 } ] } ] } ] } 对应成图 enter image description here

输入json, 输出json 这2端json结构类似, 仅仅根节点反转了, 叶子节点转成根节点, 叶子节点的父节点转成子节点, 对应成图形结构不变; 例如图片所示, 原来的根节点A为中心生成图形, 现在是根节点Q为中心生成图形; 求一段遍历算法, 完成 json–> data的转化

2个月前
回答
Ant杉 ,一杉

重新表述一下你的这个问题:

输入一颗有根树T,根为N1,以及该树中的一个节点N2,请使用DFS翻转该树,使得根变为N2,并且这两颗树的同构(拓扑结构一致)

以下有一些前置说明:

  1. 数据结构就用你的了,不过需要预处理一下,使得树的所有节点都唯一(方便指定任意节点)。unique的预处理随便写了一下:

    var uniqueFunc = (function () {
        var count = 0;
    
        return function (oldName) {
                return newName = oldName + '_' + count++;
            }
    })();
    
  2. 给出一个简易的DFS函数:

    var generalDFS = function generalDFS(currentElement, callback, parentElement) {
        callback(currentElement, parentElement);
        if ( currentElement['children'] ) {
            currentElement['children'].forEach(function (childElement) {
                generalDFS(childElement, callback, currentElement);
            })
        }
    }
    

然后,下面给出2种方法:

  1. 是先把这棵树的所有边按照双向都存储一遍,然后根据存储的边重新构造树,当然这样感觉很low
  2. 就做一次DFS,当遇到节点N2时,停住,然后反向构造新的树。

具体代码见JsFiddler,这边的显示真是坑啊。。。。。

  1. 方法1:

  1. 方法2:

2个月前评论 0分享
我来回答
无用回答
问题标签
问题修改记录
此问题在 2个月前 修改。
理由:预览和发表后的结果不一致
广告位 点击查看投放指南

我的收藏