遍历非二叉树

Question

我正试图遍历一个非二叉树.树的字符串表示形式list为:

['TOP',['S',['NP',['PRP','I'],['VP',['VBP','需要'],['NP',['NP' ,['DT','a'],['NN','flight']],['PP',['IN','from'],['NP',['NNP','Atlanta' ]],['PP',['TO','to'],['NP',['NP',['NNP','Charlotte']],['NP',['NNP', '北'],['NNP','卡罗莱纳']]]],['NP',['JJ','next'],['NNP','星期一']]]]]]

这是来自Penn Treebank.最后,我想把它变成一个二叉树,但首先我需要一种方法来遍历树,就像现在一样.

Answer 1

def traverse(tree_of_lists):
    for item in tree_of_lists:
        if isinstance(item, list):
            for x in traverse(item):
                yield x
        else:
            yield item

这是"基本"解决方案 - 可以在Python 2.7中运行,并为您提供一个可以简单循环的迭代.(在最近的Python 3.*版本中,您将使用yield from item而不是内部for循环).

该isinstance测试是不愉快的,但根据您的具体问题,它可能是从一个"子树"区分"标项目"的唯一途径.可能有更好的但你没有给我们足够的信息来告诉你.例如,如果所有"离开"(标量)都是字符串,您可能更愿意检查它(仍然是一个isinstance检查,唉!).