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

Question

我正在寻找一个好的Tree数据结构类.我遇到过这个包,但由于我相对较新的Python(不是编程),我不知道那里有没有更好的.

我想在这里听到Pythonistas的消息 - 你有一个你经常使用并会推荐的最喜欢的树脚本吗？

[编辑]

澄清一下,'Tree',我的意思是一个简单的无序树(嗯,这有点像一个递归的定义 - 但希望,这有点澄清一些事情).关于我需要的树(即用例).我正在从平面文件中读取树数据,我需要从数据构建树并遍历树中的所有节点.

Answer 1

你可以像这样构建一个很好的dicts dicts树:

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 2

我找到了一个由Brett Alistair Kromkamp编写的模块,该模块尚未完成.我完成了它并在github上公开并将其重命名为treelib(原始pyTree):

https://github.com/caesar0301/treelib

可以帮你....

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中的子生成器会有所帮助.

Answer 4

基于上面给出的使用defaultdict的单行树给出的答案,你可以使它成为一个类.这将允许您在构造函数中设置默认值,并以其他方式在其上构建.

class Tree(defaultdict):
    def __call__(self):
        return Tree(self)

    def __init__(self, parent):
        self.parent = parent
        self.default_factory = self

此示例允许您进行后引用,以便每个节点都可以引用树中的父节点.

>>> 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

接下来,您甚至可以覆盖类Tree上的__setattr__,以便在重新分配父级时,将其作为子级从父级中删除.这种模式有很多很酷的东西.

Answer 5

使用networkx库基于非循环有向图编写自己的树包装器可能是值得的 .

Answer 6

对于有序儿童的树,我通常会做一些这样的事情(虽然不那么通用,适合我正在做的事情):

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它或更现代的后代.

Answer 7

Python中另一个好用且易于使用的树实现是pyTree:https: //github.com/caesar0301/pyTree

pyTree还提供了可视化树的可能性:

Harry[harry]
|___ Jane[jane]
|    |___ Diane[diane]
|         |___ George[george]
|              |___ Jill[jill]
|         |___ Mary[mary]
|    |___ Mark[mark]
|___ Bill[bill]