首页 注册 登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐关注
› Meteor
› JSLint - a JavaScript code quality tool
› jsFiddle
› D3.js
› WebStorm
推荐书目
› JavaScript 权威指南第 5 版
› Closure: The Definitive Guide
广告
zxc337
V2EX  ›  JavaScript

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

  •   
  •   zxc337 · 2016-06-02 23:31:42 +08:00 · 6282 次点击
    这是一个创建于 3103 天前的主题，其中的信息可能已经有所发展或是发生改变。

    有如下一段 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
				        }
				    ]
                }
		    ]
        }
    ]
}

    不知道各位有没有比较好的算法实现?

    第 1 条附言  ·  2016-06-03 10:20:39 +08:00

    我再把需求抽象一下吧, 输入json为 var 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}]}'; 对应成图

    输出json为 var data='{"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}]}]}]}'; 对应成图

    输入json, 输出json结构类似, 仅仅根节点反转了, 叶子节点转成根节点, 叶子节点的父节点转成子节点, 对应成图形结构不变; 例如图片所示, 原来的根节点A为中心生成图形, 现在是根节点Q为中心生成图形;

    第 2 条附言  ·  2016-06-03 10:21:32 +08:00
    第二张图
    <img src="https://sfault-image.b0.upaiyun.com/173/993/1739937525-5750e82a8b856_articlex" />
    第 3 条附言  ·  2016-06-03 10:22:09 +08:00

    第二张图

  • name
  • size
  • children
  • JSON
    23 条回复  •  2016-06-03 16:50:03 +08:00
    zxc337
        1
    zxc337  
    OP
       2016-06-02 23:33:46 +08:00
    我在 segmentfault 上面也发了 https://segmentfault.com/q/1010000005626877 , 不知道他们为什么审核那么慢
    zxc337
        2
    zxc337  
    OP
       2016-06-02 23:40:10 +08:00
    我尝试用递归实现,没有达到效果
    ```
    var json='';
    function isArray(o) {
    return Object.prototype.toString.call(o) === '[object Array]';
    }
    function dfs(_key,o){
    if(o.children) {
    for (var v in o.children) {
    var child = o.children[v];
    if(child.name && _key == child.name) return o;
    dfs(_key,child);
    }
    }
    }


    ```
    zhouyg
        3
    zhouyg  
       2016-06-03 00:08:01 +08:00
    不太看得懂问题，把一个节点提升到变成根节点，
    然后“对 json 数据进行反转”，反转的规则是能描述下么？
    WangYanjie
        4
    WangYanjie  
       2016-06-03 00:13:51 +08:00
    递归会很简单
    1. 找到你要开始反转的节点
    2. 开始递归：输入，反转节点和直接父节点，操作，反转并更新需要反转的节点，终止条件，跟节点

    PS: 深度，广度随你，遍历的时候标记每个节点父节点和需要反转的节点即可
    shiye515
        5
    shiye515  
       2016-06-03 00:15:16 +08:00 via Android
    每个节点加个 pid 指向父节点的 id
    Magic347
        6
    Magic347  
       2016-06-03 00:28:42 +08:00
    题主在这里显然连问题的输入和输出都没有描述明确。
    暂且假设输入是一个 json 对象，输出是一个重新指定根节点所谓“反转”的 json 对象，
    由于输入是 json 对象，注意是 json 对象！因此是无法如 LS 这位仁兄所说的简单调整节点之间的父子关系的。
    因此，在鄙人看来，应首先对原 json 对象进行一次转换，转换成什么呢？转换成一个等价的无向图。
    无向图长什么样呢？题主自己其实已经贴出来了。
    有了这个等价的无向图以后，指定其中任意出度为 1 的节点作为“根节点”均可深度遍历改图，在图遍历过程中重新构建新的 json 对象即可。
    这里值得注意的是，图的深度遍历恰好符合 json 对象的重构顺序，楼主可以选一个结构相对简单的 json 对象进行实验，思路仅供参考。
    Magic347
        7
    Magic347  
       2016-06-03 01:08:52 +08:00
    来一段代码意思一下吧，
    假设有已经构建完成了一个等价于原 j 输入 son 对象的无向图，
    那么指定其中任意一个出度为 1 的节点作为新的根节点，利用无向图的深度优先遍历（遍历过程注意标记节点是否曾经被访问过），容易得到以下重构 json 对象的方法：

    def reconstruct_json(node ， visited):
    ____retval = {}
    ____for key in node.keys():
    ________retval[key] = node.values[key]
    ____visited[node] = True
    ____has_children = len(node.neighbors) > 0 and any(not visited[child] for child in node.neighbors)
    ____if has_children:
    retval["children"] = []
    ________for child in node.neighbors:
    if not visited[child]:
    ________________retval["children"].append(reconstruct_json(child, visited))
    ____return retval
    Magic347
        8
    Magic347  
       2016-06-03 01:10:43 +08:00
    def reconstruct_json(node, visited):
    ____retval = {}
    ____for key in node.keys():
    ________retval[key] = node.values[key]
    ____visited[node] = True
    ____has_children = len(node.neighbors) > 0 and any(not visited[child] for child in node.neighbors)
    ____if has_children:
    ________retval["children"] = []
    ________for child in node.neighbors:
    ____________if not visited[child]:
    ________________retval["children"].append(reconstruct_json(child, visited))
    ____return retval
    WangYanjie
        9
    WangYanjie  
       2016-06-03 02:31:14 +08:00
    @Magic347
    失眠了，不是来吵架的
    json 不是理由，你操作 json 前肯定是要转换成数据字典的。

    # 深度遍历，直到遇到你要反转的叶节点，跳出
    # 假设 stack 保存了从 root 到 leaf 的路径
    # python 写的， js 只能看看
    stack = [] # save path: root -> leaf

    root = child = stack.pop()
    root['children'] = []
    parent = stack.pop()

    parent['children'].remove(child)
    while stack:
    ----stack[-1]['children'].remove(parent)
    ----child['children'].append(parent)
    ----child, parent = parent, stack.pop()

    child['children'].append(parent)
    Magic347
        10
    Magic347  
       2016-06-03 09:49:52 +08:00
    @WangYanjie
    对原 json 对象的一次深度遍历显然是得不到你所谓的一条从 root 到 leaf 的路径的。
    深度遍历能够得到的是从 root 节点到 leaf 节点途径的所有节点，其中可能存在某两个节点之间是兄弟关系。
    而你的算法正确的前提是在这条路径上所有的节点关系都必须严格符合：前一个节点是后一个节点的父节点。
    恐怕你还得再推敲推敲。
    WangYanjie
        11
    WangYanjie  
       2016-06-03 10:57:48 +08:00
    @Magic347
    确实不能直接得到，既然已经遍历了，那么要得到从 root 到 leaf 的路径很难吗？
    Magic347
        12
    Magic347  
       2016-06-03 12:13:24 +08:00
    @WangYanjie
    需要重新扫描一遍由 root 节点到 leaf 节点深度优先遍历的序列，
    首先由 leaf 节点开始，不断向前寻找处于路径上当前节点的上一个父节点，恐怕也不是很方便吧？
    ----------------------------
    另外有一点很重要，之前疏忽一直没有提到，就是你的算法自始至终都是在重新反转和原 json 对象等价的多叉树，
    并没有实际去重构原 json 对象，你再仔细考虑考虑是不是如此？

    因为问题的关键在于， json 对象已经是树型结构的一种文本表达方式，它不具有记录节点之间父子关系的特性，说白了没有节点之间明确的指向关系。因此，你所做的工作前提还是需要具备一棵与原 json 对象结构等价的多叉树，那么你提到的反转父子节点关系的操作才有意义，而反转完成以后也仍然需要在这棵多叉树基础上重构该 json 对象，类似的方法我也已经在 reconstruct_json()中提到了。

    所以你看到了，你饶了一个大圈子，去折腾节点的父子关系，还不如一张无向关系图来的简单明了。
    因为要知道你的方法，一旦重新指定一个新的 leaf 节点作为新的 root 时，又该重新构建这棵多叉树。
    而一旦建立起无向图，至少对于给定的 1 个 json 对象而言是一劳永逸的。
    WangYanjie
        13
    WangYanjie  
       2016-06-03 12:23:47 +08:00
    ######################### 不是很方便
    parents = {}
    while True: # 遍历
    ----for child in node.children:
    --------parents[child] = node
    -------- other

    ##################### 并没有实际去重构原 json 对象
    hh
    chairuosen
        14
    chairuosen  
       2016-06-03 13:34:38 +08:00
    不太懂算法，写了个 demo 不知道对不对。
    https://jsfiddle.net/1ex04cok/
    xuzicn
        15
    xuzicn  
       2016-06-03 13:34:50 +08:00
    https://github.com/xuzicn/revertTree
    拿去不谢。

    思路很简单：
    1. plainJSON 把 JSON 拍平成一个数组，[{ level: 0, self: node }]的结构，并且返回新的根节点在 queue 里面的 index
    2. 在 queue 里面查找新的根节点到老的根节点的路径
    3. 把路径上的所有的父子关系翻转，即可得到新树

    不知到有没有 bug ，你可以测测
    xuzicn
        16
    xuzicn  
       2016-06-03 13:40:01 +08:00
    关键点在于，只有新老根节点中间这一段路径上的父子关系需要翻转，其余的父子关系照旧。查找路径的话，根据是否排序会有更多的算法
    zxc337
        17
    zxc337  
    OP
       2016-06-03 13:53:03 +08:00
    @xuzicn 行, 我测试下
    zxc337
        18
    zxc337  
    OP
       2016-06-03 15:12:23 +08:00
    @xuzicn 有个 bug, 我使用叶子节点的父节点, 作为根节点重新生成图的时候, 根节点错乱了
    xuzicn
        19
    xuzicn  
       2016-06-03 16:03:47 +08:00
    @zxc337 来个 case 推到 git 上去吧
    xuzicn
        20
    xuzicn  
       2016-06-03 16:09:06 +08:00
    草， segmentfault 底下这个回答也是够有意思的，直接抄我的代码啊
    rekulas
        21
    rekulas  
       2016-06-03 16:24:57 +08:00
    @xuzicn 确实，太恶劣了，好歹把方法名改一下，位置换一下啊
    rekulas
        22
    rekulas  
       2016-06-03 16:36:14 +08:00
    如果翻转操作很频繁，用一个标识标记顶级点是哪一个就行了，有点是翻转不消耗什么资源，缺点是最后需要输出一次 tree 结构
    xieranmaya
        23
    xieranmaya  
       2016-06-03 16:50:03 +08:00
    @xuzicn 正解
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2824 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 25ms · UTC 12:25 · PVG 20:25 · LAX 04:25 · JFK 07:25
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.