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

Question

我有这样一个数据字典：

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

它可以用来打印树。你知道吗

是否有任何方法可以使用数据字典或树边列表获取链？你知道吗

Answer 1

不是传递一个父对象，而是传递父对象的元组：

    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
}