Skip to main content
 首页 » 编程设计

python之从树数据结构中提取所有链

2024年11月01日11lori

我有一个这样的数据字典:

dic = '{"data":"Harry",  
        "children":[{"data":"Bill", 
                     "children":[]}, 
                    {"data":"Jane", 
                     "children":[{"data":"Diane", 
                                  "children":[]}, 
                                 {"data":"Mark", 
                                  "children":[]}] 
                    } 
                   ] 
       }' 

我想分别提取树层次结构中包含的所有链,即从第一个节点到每个最后一个节点的所有完整路径:

  • 哈利 -> 比尔
  • 哈利 -> 简 -> 戴安娜
  • 哈利 -> 简 -> 马克

我使用这段代码从字典中提取了树的边缘:

from __future__ import print_function 
import json 
import sys 
from treelib import Node, Tree 
 
data = '{"data":"Harry", "children":[{"data":"Bill","children":[]},{"data":"Jane","children":[{"data":"Diane","children":[]},{"data":"Mark","children":[]}]}]}' 
data = json.loads(data) 
 
# Extract tree edges from the dict 
edges = [] 
tree = Tree() 
added = set() 
 
def get_edges(treedict, parent=None): 
    name = treedict['data'] 
    added.add(name) 
 
    if parent is not None: 
        edges.append((parent, name)) 
 
    for item in treedict["children"]: 
        if isinstance(item, dict): 
            get_edges(item, parent=name) 
 
get_edges(data) 
 
#Dump edge list in Graphviz DOT format 
print('strict digraph tree {') 
for row in edges: 
    print('    {0} -> {1};'.format(*row)) 
print('}') 

树边列表如下所示:

[(u'Harry', u'Bill'), (u'Harry', u'Jane'), (u'Jane', u'Diane'), (u'Jane', u'Mark')] 

它可以用来打印树。

有没有办法使用数据字典或树边列表来获取链?

请您参考如下方法:

传递一个父元组而不是传递一个父元组:

    from __future__ import print_function 
    import json 
    import sys 
    from treelib import Node, Tree 
 
    data = '{"data":"Harry", "children":[{"data":"Bill","children":[]},{"data":"Jane","children":[{"data":"Diane","children":[]},{"data":"Mark","children":[]}]}]}' 
    data = json.loads(data) 
 
    # Extract tree edges from the dict 
    edges = [] 
    tree = Tree() 
    added = set() 
 
 
    def get_edges(treedict, parent=()): 
        name = treedict['data'] 
        added.add(name) 
 
        if parent is not None and not treedict["children"]: 
            edges.append((parent)+(name,)) 
 
        for item in treedict["children"]: 
            if isinstance(item, dict): 
                get_edges(item, parent=parent + (name,)) 
 
    get_edges(data) 
 
    #Dump edge list in Graphviz DOT format 
    print('strict digraph tree {') 
    for row in edges: 
        print('-->'.join(row)) 
    print('}') 

输出:

strict digraph tree { 
    Harry-->Bill 
    Harry-->Jane-->Diane 
    Harry-->Jane-->Mark 
}