python - 从堆栈跟踪到树

Question

我现在一直在绞尽脑汁寻找一种简单的递归方法来做到这一点 - 假设我有一个堆栈的一系列状态，看起来像这样，作为列表的列表:

[ 
[a]
[a,b]
[a,b,c]
[a,b]
[a,b,d]
[a,b]
[a]
[a,e]
]

我想将其表示为一棵树，但使用嵌套列表层，而不为树定义新类。

上面的树格式可能看起来像这样

[a, [b, [c],
        [d]],
    [e]    ]

本质上是说，由于 c 和 d 在 b 之后，因此它们是 b 的子级，并且由于它们在堆栈跟踪中没有追随者，因此它们后面没有任何内容(或者表示没有子级的空列表)。所以这也足够了:

[a, [b, [c, []],
        [d, []],
    [e, []      ]

基本上代表的树是

   a
  / \
 e   b
    / \
   c   d

但完全没有类(class)。是的，我知道这是不干净的，并且类可能是执行此操作的干净方法，但我对没有类的解决方案感兴趣。

Answer 1

这里可以实现您想要的功能，同时将每个节点放入它自己的列表中，恕我直言，这更具可读性和可用性:

input =  
[['a'],
 ['a', 'b'],
 ['a', 'b', 'c'],
 ['a', 'b'],
 ['a', 'b', 'd'],
 ['a', 'b'],
 ['a'],
 ['a', 'e']]

output = []
item_node = {}
for lst in input:
    for i in range(len(lst)):
        if lst[i] not in item_node:
            item_node[lst[i]] = [lst[i], []]
            if i == 0:
                output.append(item_node[lst[i]])
            else:
                item_node[lst[i-1]][1].append(item_node[lst[i]])

Out[47]: [['a', [['b', [['c', []], ['d', []]]], ['e', []]]]]

要首先使用相同的设置以您想要的格式获取它:

for lst in input:
    for i in range(len(lst)):
        if lst[i] not in item_node:
            item_node[lst[i]] = [lst[i]]
            if i == 0:
                output.append(item_node[lst[i]])
            else:
                item_node[lst[i-1]].append(item_node[lst[i]])


Out[58]: [['a', ['b', ['c'], ['d']], ['e']]]

要获得第二个选项:

for lst in input:
    for i in range(len(lst)):
        if lst[i] not in item_node:
            item_node[lst[i]] = []
            if i == 0:
                output.append(lst[i])
                output.append(item_node[lst[i]])
            else:
                item_node[lst[i-1]].append(lst[i])
                item_node[lst[i-1]].append(item_node[lst[i]])
Out[54]: ['a', ['b', ['c', [], 'd', []], 'e', []]]