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

[zxc337]

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

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

[zxc337]

我在 segmentfault 上面也发了 https://segmentfault.com/q/1010000005626877 , 不知道他们为什么审核那么慢

[zxc337]

我尝试用递归实现,没有达到效果
```
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]

不太看得懂问题，把一个节点提升到变成根节点，
然后“对 json 数据进行反转”，反转的规则是能描述下么？

[WangYanjie]

递归会很简单
1. 找到你要开始反转的节点
2. 开始递归：输入，反转节点和直接父节点，操作，反转并更新需要反转的节点，终止条件，跟节点

PS: 深度，广度随你，遍历的时候标记每个节点父节点和需要反转的节点即可

[shiye515]

每个节点加个 pid 指向父节点的 id

[Magic347]

题主在这里显然连问题的输入和输出都没有描述明确。
暂且假设输入是一个 json 对象，输出是一个重新指定根节点所谓“反转”的 json 对象，
由于输入是 json 对象，注意是 json 对象！因此是无法如 LS 这位仁兄所说的简单调整节点之间的父子关系的。
因此，在鄙人看来，应首先对原 json 对象进行一次转换，转换成什么呢？转换成一个等价的无向图。
无向图长什么样呢？题主自己其实已经贴出来了。
有了这个等价的无向图以后，指定其中任意出度为 1 的节点作为“根节点”均可深度遍历改图，在图遍历过程中重新构建新的 json 对象即可。
这里值得注意的是，图的深度遍历恰好符合 json 对象的重构顺序，楼主可以选一个结构相对简单的 json 对象进行实验，思路仅供参考。

[Magic347]

来一段代码意思一下吧，
假设有已经构建完成了一个等价于原 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]

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]

@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]

@WangYanjie
对原 json 对象的一次深度遍历显然是得不到你所谓的一条从 root 到 leaf 的路径的。
深度遍历能够得到的是从 root 节点到 leaf 节点途径的所有节点，其中可能存在某两个节点之间是兄弟关系。
而你的算法正确的前提是在这条路径上所有的节点关系都必须严格符合：前一个节点是后一个节点的父节点。
恐怕你还得再推敲推敲。

[WangYanjie]

@Magic347
确实不能直接得到，既然已经遍历了，那么要得到从 root 到 leaf 的路径很难吗？

[Magic347]

@WangYanjie
需要重新扫描一遍由 root 节点到 leaf 节点深度优先遍历的序列，
首先由 leaf 节点开始，不断向前寻找处于路径上当前节点的上一个父节点，恐怕也不是很方便吧？
----------------------------
另外有一点很重要，之前疏忽一直没有提到，就是你的算法自始至终都是在重新反转和原 json 对象等价的多叉树，
并没有实际去重构原 json 对象，你再仔细考虑考虑是不是如此？

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

所以你看到了，你饶了一个大圈子，去折腾节点的父子关系，还不如一张无向关系图来的简单明了。
因为要知道你的方法，一旦重新指定一个新的 leaf 节点作为新的 root 时，又该重新构建这棵多叉树。
而一旦建立起无向图，至少对于给定的 1 个 json 对象而言是一劳永逸的。

[WangYanjie]

######################### 不是很方便
parents = {}
while True: # 遍历
----for child in node.children:
--------parents[child] = node
-------- other

##################### 并没有实际去重构原 json 对象
hh

[chairuosen]

不太懂算法，写了个 demo 不知道对不对。
https://jsfiddle.net/1ex04cok/

[xuzicn]

https://github.com/xuzicn/revertTree
拿去不谢。

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

不知到有没有 bug ，你可以测测

[xuzicn]

关键点在于，只有新老根节点中间这一段路径上的父子关系需要翻转，其余的父子关系照旧。查找路径的话，根据是否排序会有更多的算法

[zxc337]

@xuzicn 行, 我测试下

[zxc337]

@xuzicn 有个 bug, 我使用叶子节点的父节点, 作为根节点重新生成图的时候, 根节点错乱了

[xuzicn]

@zxc337 来个 case 推到 git 上去吧

[xuzicn]

草， segmentfault 底下这个回答也是够有意思的，直接抄我的代码啊