遍历非二叉树

-4

我试图遍历一个非二叉树。树的字符串表示，作为一个list，是：遍历非二叉树

[ '顶部'，[ 'S'，[ 'NP'，[ 'PRP'， 'I']]，[ 'VP'， ['VBP'，'need']，['NP'， ['NP'，['DT'，'a']，['NN'，'flight']]，['PP'，['IN ''''，''''，''，''，''，''，'''，'''，''NP'，['NP'，''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ['NNP'， 'Charlotte']]，['NP'，['NNP'，'North']，['NNP'，'Carolina']]]]，['NP'， ['JJ' ，'next']，['NNP'，'Monday']]]]]]

这是来自Penn Treebank。最终，我想把它变成一棵二叉树，但首先我需要一种方法来遍历树。

来源

2014-12-23 Adam_G

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检查，唉！）。

来源

2014-12-23 17:35:24

你是什么意思的“标量项目”？ –

@Adam_G是单个值，而不是列表。 – Alexandru

也被称为“一片叶子”，这将是除了树中的“子树”之外的任何表示形式（看起来像所有的子树都是列表，并且所有的叶/标量都是字符串，但这就是从这个例子中推断出来，因此有点脆弱，缺少一个明确声明的规范）。 –

-2

遍历树有很多种方法。选项包括：

前序遍历 - 发出当前节点，然后递归遍历其子
后序遍历 - 递归遍历当前节点，则发出当前节点
中序遍历 - 递归遍历左边的孩子。然后发出当前节点。最后，穿过正确的孩子。意味着一棵二叉树，但如果你有办法将孩子分成“左”和“右”组，它可以适应一般树。

您可以通过它添加到已累积列表“发出”一个节点，但更好的方法是使用一个发电机和yield的节点。

您会在Wikipedia page on tree traversal上找到这些和其他选项。选一个满足你的需求。

来源

2014-12-23 17:37:07

嗯，这是一个非常基本的问题，Google很快就能找到。此外，还有很多遍历树的方法，并且该问题没有提供关于需要哪种方法的指示。 –

遍历非二叉树

回答

相关问题