寻找一个好的Python树数据结构
我正在寻找一个好的树型数据结构类。 我遇到过这个包 ，但是因为我对Python比较新（不是编程），所以我不知道是否有更好的东西。
我想在这里听到Pythonistas – 你有一个最喜欢的树脚本，你经常使用，并会build议？
[编辑]
为了弄清楚，用“树”来表示一个简单的无序树（嗯，这是一个recursion的定义 – 但希望有点澄清的事情）。 关于我需要什么树（即用例）。 我正在从平面文件中读取树数据，我需要从数据中构build树并遍历树中的所有节点。
滚动你自己的。 例如，只需将您的树build模为列表的列表。 你应该详细说明你的具体需求，然后才能提供更好的build议。
为了回应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 一个问题就是这个recursion实现是O（n log n）。 它适用于我必须处理的所有树木。 也许在Python 3中的子生成器会有所帮助。
你可以build立一个像这样的字典的好树：
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'})})
欲了解更多信息，请看这个要点 。
我发现Brett Alistair Kromkamp写的一个模块没有完成。 我完成了它，并在github上公布，并将其更名为treelib （原始pyTree ）：
https://github.com/caesar0301/treelib
愿它帮助你…
对于一个有秩序的孩子的树，我通常会做这样的事情（虽然不太一般，适合于我所做的）：
class TreeNode(list): def __init__(self, iterable=(), **attributes): self.attr = attributes list.__init__(self, iterable) def __repr__(self): return '%s(%s, %r)' % (type(self).__name__, list.__repr__(self), self.attr)
你可以做一些比较dict或使用DictMixin或更现代的后裔，如果你想无钥匙的孩子访问。
另外一个很好用的Python实现树是pyTree： https ： //github.com/caesar0301/pyTree
pyTree也提供可视化树的可视性：
Harry[harry] |___ Jane[jane] | |___ Diane[diane] | |___ George[george] | |___ Jill[jill] | |___ Mary[mary] | |___ Mark[mark] |___ Bill[bill]
使用networkx库，基于非循环有向图来编写自己的树封装可能是值得的。
这是我正在做的事情。
class Tree: def __init__(self, value, *children): '''Singly linked tree, children do not know who their parent is. ''' self.value = value self.children = tuple(children) @property def arguments(self): return (self.value,) + self.children def __eq__(self, tree): return self.arguments == tree.arguments def __repr__(self): argumentStr = ', '.join(map(repr, self.arguments)) return '%s(%s)' % (self.__class__.__name__, argumentStr)
（用作示例值的数字）： t = Tree(1, Tree(2, Tree(4)), Tree(3, Tree(5)))
build立在上面用单行树使用defaultdict给出的答案 ，你可以使它成为一个类。 这将允许您在构造函数中设置默认值，并以其他方式构build它。
class Tree(defaultdict): def __call__(self): return Tree(self) def __init__(self, parent): self.parent = parent self.default_factory = self
这个例子允许你创build一个反向引用，以便每个节点可以引用它的父树。
>>> t = Tree(None) >>> t[0][1][2] = 3 >>> t defaultdict(defaultdict(..., {...}), {0: defaultdict(defaultdict(..., {...}), {1: defaultdict(defaultdict(..., {...}), {2: 3})})}) >>> t[0][1].parent defaultdict(defaultdict(..., {...}), {1: defaultdict(defaultdict(..., {...}), {2: 3})}) >>> t2 = t[0][1] >>> t2 defaultdict(defaultdict(..., {...}), {2: 3}) >>> t2[2] 3
接下来，您甚至可以重写类树上的__setattr__，以便在重新分配父项时，将其作为子项从父项中移除。 这种模式很多很酷的东西。
BTrees会帮忙吗？ 它们是Zope对象数据库代码的一部分。 下载整个ZODB包是有点矫枉过正的，但是我希望BTrees模块至less可以分开。
我认为，从我自己在更先进的数据结构方面的经验来看，在这里可以做的最重要的事情就是对数据结构的一般概念有一个很好的了解。 如果您了解概念背后的基本机制，那么实施适合您问题的解决scheme将非常容易。 这里有很多很好的来源来描述这个概念。 多年前在这个特殊问题上“拯救”我的是“计算机程序devise艺术”中的第2.3节。
