时间戳

首页 > 解决方案 > 根据二叉树逐级制作嵌套列表

python - 根据二叉树逐级制作嵌套列表

问题描述

使用二叉树，我试图逐级制作嵌套列表。这是我所做的：

arrows = [("modifier","adverb1"),("noun","modifier"),("verb","noun"),("verb","adverb2"),("root","verb")]

dom_list = list(dict.fromkeys([a[0] for a in arrows]))
dom_list.pop()

depth = []
for a in dom_list:
    MC = [v[1] for v in arrows if v[0] == a]
    depth.append(MC)

con = []
for i in range(len(dom_list)):
    c = [dom_list[i], depth[i]]
    con.append(c)

代码行导致：

[['modifier', ['adverb1']],
 ['noun', ['modifier']],
 ['verb', ['noun', 'adverb2']]]

我想用这个输入做一个嵌套列表，如：

['root', ['verb', ['noun', ['modifier', ['adverb1']], 'adverb2']]]

有没有办法做到这一点？任何帮助将不胜感激。

标签： pythonpython-3.x

解决方案

当然不是我最优化的代码，但它适用于您提供的数据，因为我了解您的问题。也许这可以帮助您找出更优雅的解决方案：

def flat_gen(x):

    # Flattens a nested list, taken from here but forgot the post

    def iselement(e):
        return not(isinstance(e, collections.Iterable) and not isinstance(e, str))
    for el in x:
        if iselement(el):
            yield el
        else:
            yield from flat_gen(el)  

tmp = [list(x) for x in arrows]

tmp_new = []

for a in tmp:
    
    for b in tmp:
        
        if b[1] == a[0]:
            
            b[1] = a
            
            tmp_new.append(b)
            
        else: 
            
            tmp_new.append(b)
            
            
# Find longest chain
idx_longest = [len(list(flat_gen(e))) for e in tmp_new].index(max([len(list(flat_gen(e))) for e in tmp_new]))
longest = tmp_new[idx_longest]

# Identify missing elements in longest chain
missing = set(flat_gen(arrows)).difference(list(set(flat_gen(longest))))


for m in missing:
    
    for a in arrows:
        
        if m in a:
            
            outer = [""]
            i = 0
            outer[i] = longest
            found = False
            
            while not found:
            
                print(a[0])
                print(outer[i])
                
                inner = outer[i][1]
                
                if outer[i][0] == a[0]:
                    
                    # Found position where to insert
                    outer[i].append(a[1])
                    found = True
                    
                else:
                    
                    # Continue searching
                    outer.append(inner)
                    i += 1
                    
            
a = list(a)
a[1] = outer[i]

print(a)

回报：

['root', ['verb', ['noun', ['modifier', 'adverb1']], 'adverb2']]

推荐阅读