从分支列表重建树

Question

给定一个包含多个子列表的列表，每个子列表代表一条树枝。我们的目标是写一个Python程序，从这些树枝中重建出一棵树。这里的“树枝”指的是从树的根节点开始，一直到叶子节点的那条路径。假设这个主列表的格式是这样的：

branches = [b_1 , b_2 , b_3 , ... , b_n]

这里树枝的数量等于叶子节点的数量n。每条树枝包含从树的根节点到叶子节点的节点列表，顺序是从根到叶：

b_i = [root,n_1,n_2,n_3,...,leaf_i]

我们的目标是把所有的列表合并成一个字典，这个字典能够表示树的结构。每个节点应该有两个键值对：名字和孩子。名字的值是节点的名称，而孩子的值是一个节点列表（这些节点也是字典，包含名字和孩子）。如果没有这种特定的结构，这个问题就和如何将列表转换为嵌套字典非常相似。

例如，如果列表是：

branches=[[root,n1,l1],[root,n1,l2],[root,n2,l3],[root,n2,l4]]

我们希望得到一个像这样的字典：

treeDict = {'name':root,'children':
              [
                {'name':n1,'children':[
                    {'name':l1,'children':[]},
                    {'name':l2,'children':[]}]},
                {'name':n2,'children':[
                    {'name':l3,'children':[]},
                    {'name':l4,'children':[]}]}
              ]
           }

它表示的就是这棵树：

        root
      /     \
     n1      n2
    /  \    /  \
   l1   l2 l3   l4

Answer 1

这是一种使用递归来处理字典的方法：

import pprint


def traverse(root, branch):
    if not branch:
        return
    if branch[0] not in root:
        root[branch[0]] = {}
    traverse(root[branch[0]], branch[1:])


# Or rather, uglify
def prettify(root):
    res = []
    for k, v in root.iteritems():
        d = {}
        d['name'] = k
        d['children'] = prettify(v)
        res.append(d)
    return res


d = {}
branches = [['root','n1','l1'],['root','n1','l2'],['root','n2','l3'],['root','n2','l4']]
for b in branches:
    traverse(d, b)
pprint.pprint(d)
pprint.pprint(prettify(d))

输出结果：

# The compact representation
{'root': {'n1': {'l1': {}, 'l2': {}}, 'n2': {'l3': {}, 'l4': {}}}}

# The desired representation
[{'children': [{'children': [{'children': [], 'name': 'l2'},
                             {'children': [], 'name': 'l1'}],
                'name': 'n1'},
               {'children': [{'children': [], 'name': 'l4'},
                             {'children': [], 'name': 'l3'}],
                'name': 'n2'}],
  'name': 'root'}]