基于关系数据生成层次结构的过程？
我有一个csv的雇员id，名字，和一个引用列与他们的直接经理的id，说如下
emp_id, emp_name, mgr_id
1,The Boss,,
2,Manager Joe,1
3,Manager Sally,1
4,Peon Frank,2
5,Peon Jill,2
6,Peon Rodger,3
7,Peon Ralph,3我希望能够生成一个(json)对象，它表示这个结构，类似于
DATA = {
"parent": "The Boss",
"children: [
{
"parent": "Manager Joe",
"children": [ {"parent": "Peon Frank"}, {"parent": "Peon Jill"} ]
},
{
"parent": "Manager Sally",
"children": [ {"parent": "Peon Rodger"}, {"parent": "Peon Ralph" } ]
}]
}因此，从数据来看，没有mgr_id的条目代表了类似于首席执行官或领导者的内容。
所以只是收集一些想法..。我知道这可以用一些具有树遍历的树数据结构来表示，从而生成正确的输出。解析器必须负责插入到树中。也许孩子的数量会给你一个体重？只是集思广益。我不知道如何围绕这样一个事实，即可以用子对象构造多个对象。
是否有一个算法可以解析我没有想到的这个结构？下降到孩子们身上似乎相对简单。我脑子里没看到这个，我需要一些帮助。谢谢
回答 3
Software Engineering用户
发布于 2014-10-28 02:40:14
从平地上创造结构有几种方法。递归是最好的之一。这个程序使用它，初步的步骤是找出哪些项目是父母。
虽然这种策略与语言无关，但每种语言都有不同的数据结构和构建块的细节。我用Python实现了这种方法。
注，大约一半的代码是为了显示和演示目的，所以您可以跟随并查看算法是如何工作的。生产时，可免费拆下这些零件。
Oh...and，我把标签从“家长”改为“名字”，把“孩子”改成“报告”，因为我觉得这更令人愉快。当然，你可以选择任何你喜欢的。
from pprint import pprint
from random import shuffle
from collections import defaultdict
import json
def show_val(title, val):
"""
Debugging print helpler.
"""
sep = '-' * len(title)
print "\n{0}\n{1}\n{2}\n".format(sep, title, sep)
pprint(val)
# ORIGINAL NAMES: emp_id, emp_name, mgr_id
# SIMPLIFIED NAMES: eid, name, mid
text = """
323,The Boss,
4444,Manager Joe,323
3,Manager Sally,323
4,Peon Frank,4444
33,Peon Dave,3
5,Peon Jill,4444
6,Peon Rodger,3
7,Peon Ralph,3
233,Clerk Jane,99
99,Supervisor Henri,3
"""
# parse text into lines
lines = [ l.strip() for l in text.strip().splitlines() ]
# construct list of people tuples
people = [ tuple(l.split(',')) for l in lines ]
# for demonstration and testing only, shuffle the results
shuffle(people)
show_val("randomized people", people)
# contstruct list of parents
parents = defaultdict(list)
for p in people:
parents[p[2]].append(p)
show_val("parents", parents)
def buildtree(t=None, parent_eid=''):
"""
Given a parents lookup structure, construct
a data hierarchy.
"""
parent = parents.get(parent_eid, None)
if parent is None:
return t
for eid, name, mid in parent:
report = { 'name': name }
if t is None:
t = report
else:
reports = t.setdefault('reports', [])
reports.append(report)
buildtree(report, eid)
return t
data = buildtree()
show_val("data", data)
show_val("JSON", json.dumps(data))运行此操作将显示以下输出：
-----------------
randomized people
-----------------
[('233', 'Clerk Jane', '99'),
('4444', 'Manager Joe', '323'),
('33', 'Peon Dave', '3'),
('6', 'Peon Rodger', '3'),
('99', 'Supervisor Henri', '3'),
('3', 'Manager Sally', '323'),
('5', 'Peon Jill', '4444'),
('323', 'The Boss', ''),
('4', 'Peon Frank', '4444'),
('7', 'Peon Ralph', '3')]
-------
parents
-------
defaultdict(<type 'list'>, {'99': [('233', 'Clerk Jane', '99')], '323': [('4444', 'Manager Joe', '323'), ('3', 'Manager Sally', '323')], '3': [('33', 'Peon Dave', '3'), ('6', 'Peon Rodger', '3'), ('99', 'Supervisor Henri', '3'), ('7', 'Peon Ralph', '3')], '4444': [('5', 'Peon Jill', '4444'), ('4', 'Peon Frank', '4444')], '': [('323', 'The Boss', '')]})
----
data
----
{'name': 'The Boss',
'reports': [{'name': 'Manager Joe',
'reports': [{'name': 'Peon Jill'}, {'name': 'Peon Frank'}]},
{'name': 'Manager Sally',
'reports': [{'name': 'Peon Dave'},
{'name': 'Peon Rodger'},
{'name': 'Supervisor Henri',
'reports': [{'name': 'Clerk Jane'}]},
{'name': 'Peon Ralph'}]}]}
----
JSON
----
'{"name": "The Boss", "reports": [{"name": "Manager Joe", "reports": [{"name": "Peon Jill"}, {"name": "Peon Frank"}]}, {"name": "Manager Sally", "reports": [{"name": "Peon Dave"}, {"name": "Peon Rodger"}, {"name": "Supervisor Henri", "reports": [{"name": "Clerk Jane"}]}, {"name": "Peon Ralph"}]}]}'一些初步工作:它还使用print来帮助显示嵌套的数据结构。我们通常通过数据库连接来获取数据，这里我们只是从静态文本中解析数据。最后，虽然您提供的数据排列得很好，老板位于顶部，员工id数字(简化)问题最低，但我想确认代码可以按任何顺序工作。因此，我修改了一些id数字以反映非顺序分配，并引入了random.shuffle来随机化数据的顺序。您不会在生产中这样做，但是作为测试的一部分，它增加了设计而不是偶然的逻辑工作的信心。
Software Engineering用户
发布于 2014-10-28 01:56:10
您有一个CSV文件作为持久化的形式。还有其他方法，例如SQLite，您可能希望研究这些方法，使您能够更好地查询结构，但是您仍然会遇到这样的问题:要构建完整的树结构来序列化，则需要具有完整的树结构。
在使用CSV时，您需要读取每一行，构建相应的树结构，然后将其写回，可能需要使用一个用于json序列化的库。注意到你有一些红宝石，所以，这可能看起来类似于答案在Ruby对象和序列化(没有Rails)和阅读，CSV宝石。不过，这只是一个例子，对于每一种具有远程实用价值的语言，都存在这样的CSV解析器和JSON序列化目标。
这就是它的真正归宿。你有可能有这样的东西：
1,The Boss,,
2,Founder Dev,7
3,Manager Joe,1
4,Peon Frank,3
5,Peon Jill,3
6,Peon Rodger,7
7,Manager Sally,1因此，在创建json来序列化它之前，您必须阅读所有这些内容。这是无可奈何的。
现在，csv中可能有一种不同的结构，它允许您执行一些更有用的查询，并且无需构建完整的三种结构即可使用。
嵌套集 (也可以看作是修正预序树 )可能很有用。
这棵树是这样的：
1 Boss 14
2 Manager Sally 7 8 Manager Joe 13
3 Dev 4 | 5 Rodger 6 9 Frank 10 | 11 Jill 12相应的文件将被写成：
# name L R
Boss, 1, 14
Sally, 2, 7
Dev, 3, 4
Rodger, 5, 6
Joe, 8, 13
Frank, 9, 10
Jill, 11, 12有了这棵树，人们就可以通过查找R-L > 1所在的所有行来做‘查找所有经理’之类的事情。或者，“找到每个人都要向莎莉汇报”，方法是找到L > 2 and R < 7所在的所有行。向给定人员报告的人数是(R-L-1)/2。这使得针对树的特定问题能够被更快地读取(而不需要构建树本身)。
与组织树的邻接表方法相比，修改后的预顺序树确实需要花费大量的代码行。插入会将数字在整个地方移动。例如，如果萨利让另一个人向她报告，那么此人的值为7,8，您需要修改每个人的if(L > 7) L = L + 2和if (R > 7) R = R + 2。
Software Engineering用户
发布于 2020-02-20 18:07:22
乔纳森·尤尼斯( Jonathan )的解决方案非常干净，易于遵循。在构造父母列表时，我会从父字典的值端分割父信息。而不是这样：
# contstruct list of parents
parents = defaultdict(list)
for p in people:
parents[p[2]].append(p)
show_val("parents", parents)我会有这个：
# contstruct list of parents
parents = defaultdict(list)
for p in people:
parents[p[2]].append(p[:-1])
show_val("parents", parents)因为我要删除经理id，所以我会相应地调整buidtree函数：
(我所做的只是在for循环中删除中间变量；我发现它更易读。如果我们不这样做，我们也会得到一个错误)
def buildtree(t=None, parent_eid=''):
"""
Given a parents lookup structure, construct
a data hierarchy.
"""
parent = parents.get(parent_eid, None)
if parent is None:
return t
for eid, name in parent:
report = {'name': name}
if t is None:
t = report
else:
reports = t.setdefault('reports', [])
reports.append(report)
buildtree(report, eid)
return t因此，当我再次运行脚本时，我得到了以下输出：
-----------------
randomized people
-----------------
[('6', 'Peon Rodger', '3'),
('323', 'The Boss', ''),
('33', 'Peon Dave', '3'),
('4444', 'Manager Joe', '323'),
('7', 'Peon Ralph', '3'),
('4', 'Peon Frank', '4444'),
('233', 'Clerk Jane', '99'),
('99', 'Supervisor Henri', '3'),
('5', 'Peon Jill', '4444'),
('3', 'Manager Sally', '323')]
-------
parents
-------
defaultdict(<class 'list'>,
{'': [('323', 'The Boss')],
'3': [('6', 'Peon Rodger'),
('33', 'Peon Dave'),
('7', 'Peon Ralph'),
('99', 'Supervisor Henri')],
'323': [('4444', 'Manager Joe'), ('3', 'Manager Sally')],
'4444': [('4', 'Peon Frank'), ('5', 'Peon Jill')],
'99': [('233', 'Clerk Jane')]})
----
data
----
{'name': 'The Boss',
'reports': [{'name': 'Manager Joe',
'reports': [{'name': 'Peon Frank'}, {'name': 'Peon Jill'}]},
{'name': 'Manager Sally',
'reports': [{'name': 'Peon Rodger'},
{'name': 'Peon Dave'},
{'name': 'Peon Ralph'},
{'name': 'Supervisor Henri',
'reports': [{'name': 'Clerk Jane'}]}]}]}
----
JSON
----
('{"name": "The Boss", "reports": [{"name": "Manager Joe", "reports": '
'[{"name": "Peon Frank"}, {"name": "Peon Jill"}]}, {"name": "Manager Sally", '
'"reports": [{"name": "Peon Rodger"}, {"name": "Peon Dave"}, {"name": "Peon '
'Ralph"}, {"name": "Supervisor Henri", "reports": [{"name": "Clerk '
'Jane"}]}]}]}')https://softwareengineering.stackexchange.com/questions/261074
复制相似问题
腾讯云开发者
