时间戳

首页 > 解决方案 > 从树数据结构中提取所有链

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

问题描述

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

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')]

它可以用来打印树。

反正有没有使用数据字典或树边缘列表来获取链？

标签： pythontree

解决方案

而不是传递一个父级，而是传递一个父级元组：

    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
}

推荐阅读