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

Question

我在找一个好的树形数据结构类。我发现了这个包，但是因为我对Python还比较陌生（其实对编程也不太懂），所以不太确定有没有更好的选择。

我想听听这里的Python爱好者们，你们有没有常用的树形脚本，能推荐给我的吗？

[编辑]

为了更清楚，我说的“树”是指一种简单的无序树（嗯，这有点自我定义的感觉，但希望能稍微解释清楚）。关于我需要这个树的用途，我是从一个平面文件中读取树形数据，然后需要根据这些数据构建一棵树，并遍历树中的所有节点。

Answer 1

我发现了一个由Brett Alistair Kromkamp写的模块，但它没有完成。我把它完成了，并在github上公开了，改名为treelib（原来的名字是pyTree）：

https://github.com/caesar0301/treelib

希望这对你有帮助……

Answer 2

你可以像这样构建一个漂亮的字典树，也就是字典里面还有字典：

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'})}) 

想了解更多信息，可以看看 这个链接。

Answer 3

自己动手做吧。比如，你可以把树结构看作一个列表的列表。在别人能给出更好的建议之前，你需要先明确自己的具体需求。

针对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 log n)。我处理的所有树结构用这个方法都没问题。也许Python 3中的子生成器会有所帮助。