寻找一个好的Python树数据结构

Question

我正在寻找一个好的树数据结构类。我遇到过this package，但是由于我对Python还比较陌生（不是编程），我不知道是否还有更好的。

我想听听这里的Pythonistas——你有没有一个最喜欢的树脚本，你经常使用，并会推荐？

[编辑]

为了澄清，我说的“树”是指一个简单的无序树（嗯，这是一个递归的定义——但希望它能稍微澄清一些事情）。关于我需要树做什么（即用例）。我从一个平面文件中读取树数据，我需要从数据中构建树并遍历树中的所有节点。

Answer 1

你可以建立一个很好的字典树，如下所示：

import collections

def Tree():
    return collections.defaultdict(Tree)

它可能不是你想要的，但它很有用！值仅保存在叶节点中。下面是它的工作原理示例：

>>> t = Tree()
>>> t
defaultdict(<function tree at 0x2142f50>, {})
>>> t[1] = "value"
>>> t[2][2] = "another value"
>>> t
defaultdict(<function tree at 0x2142f50>, {1: 'value', 2: defaultdict(<function tree at 0x2142f50>, {2: 'another value'})}) 

有关更多信息，请查看the gist。

Answer 2

自己滚吧。例如，只需将树建模为列表列表。在人们提供更好的推荐之前，你应该详细说明你的具体需求。

针对HelloGoodbye的问题，这是一个迭代树的示例代码。

def walk(node):
    """ iterate tree in pre-order depth-first search order """
    yield node
    for child in node.children:
        for n in walk(child):
            yield n

一个问题是这个递归实现是O（n logn）。这对我要对付的所有树木都很管用。也许Python 3中的子生成器会有所帮助。

Answer 3

我发现了一个由Brett Alistair Kromkamp编写的模块，它没有完成。我完成了它并在github上公开，并将其重命名为treelib（原始的pyTree）：

https://github.com/caesar0301/treelib

希望它能帮助你。。。。