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

Question

我正在寻找一款好的树形数据结构类。我发现了这个包，但由于我对Python相对较新（不是编程），我不知道还有没有更好的选择。

我想听听在这里的Python专家们的意见——你们是否有一个经常使用并且可以推荐的树形脚本？

[编辑]

为了澄清，“树”指的是简单的无序树（嗯，这有点递归定义——但希望这样能够澄清问题）。关于我需要树的用途（即用例），我正在从一个扁平文件中读取树状数据，需要从数据建立一棵树并遍历树中的所有节点。

- morpheous

---

至少三个重复...https://dev59.com/nXE95IYBdhLWcg3wDpcG 以及 https://dev59.com/UXE95IYBdhLWcg3wUcVn?rq=1 - eric

与此同时，有一个简单、轻量级且可扩展的树形数据结构：http://anytree.readthedocs.io/en/latest/ - c0fec0de

@c0fec0de 最好声明一下你是推荐的 anytree 包的作者。 - jarmod

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

更多信息请查看这个要点。

- Stefan

---

哇，使用defaultdict是一个绝妙的主意！ - laike9m

很好，我会一直在setter中使用try except。 - Jimmy Kane

缺点是添加与树操作相关的方法非常棘手。此外，在维基百科中，这被称为“自动存活”：https://en.wikipedia.org/wiki/Autovivification#Python - denfromufa

Answer 2

我发现了一个由Brett Alistair Kromkamp编写但未完成的模块。我对其进行了完善，并在Github上公开，将其重命名为treelib（原名pyTree）：

 

https://github.com/caesar0301/treelib

 

希望它能对你有所帮助....

- caesar0301

---

许可证是GPL，真遗憾。 - denfromufa

当我甚至不知道许可证是什么意思时，就已经授予了我这个许可证。我知道它是一个简单但有用的模块。自版本1.3.0起，我将其重新分发为Apache许可证。现在您可以在需要它的地方使用它，并声明原始版权信息。 - caesar0301

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中使用子生成器可能会更好。

- Wai Yip Tung

---

你如何以“Pythonic”的方式循环遍历这样一棵树中的所有元素？ - HelloGoodbye

通常使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历树。我通常使用DFS实现生成器，例如def walk(tree): ... - Wai Yip Tung

DFS和BFS是什么？这些缩写对我来说很新。 - HelloGoodbye

DFS是深度优先搜索。它用于树的遍历，包括前序、中序或后序遍历。BFS是广度优先搜索。它用于树的层次遍历。 - Dane White

添加了深度优先搜索的示例代码。 - Wai Yip Tung

深度优先搜索意味着在访问节点的兄弟之前，首先访问其子节点。因此，如果你有 [ A, [ B, [C, D] ], [ E, [ F, G ] ] ]，假设你在访问 E 之前访问了 B，那么你也会在访问 E 之前访问 C 和 D。广度优先搜索意味着在访问任何子节点之前，首先访问同一层级的所有节点，因此在访问 C、D、F 或 G 的任何一个之前，B 和 E 都将被访问。 - Mark Reed

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__方法，以便在重新分配父级时，将其从该父级的子项中删除。这种模式有很多很酷的用途。

- Sandy Chapman

---

在上面的例子中，t [0] [1] [2] 的父级已经损坏。AttributeError：'int'对象没有属性'parent'。 - MatthieuBizien

@oao 这并没有出错。你正在指定 t[0][1][2] = 3。因此，t[0][1][2] 不会成为 defaultdict 类型，而是成为 Number 类型（因为 defaultdict 用于为缺失的元素创建默认值）。如果你想让它成为 defaultdict，则需要在不进行赋值的情况下使用 t[0][1][2]。 - Sandy Chapman

Answer 5

对于具有有序子节点的树，我通常会做类似于这样的事情（虽然不太通用，但适合我的工作）：

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或其更现代的后继来完成类似的操作。

- Matt Anderson

Answer 6

也许编写自己的树包装器，基于使用networkx库的无环有向图，会更值得一试。

- Andrew Walker

Answer 7

这是我正在工作的一个项目。

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

- Aaron Robson

Answer 8

BTrees 能帮上忙吗？它们是 Zope 对象数据库代码的一部分。下载整个 ZODB 包有点过头了，但我希望 BTrees 模块至少能够在某种程度上分离出来。

- Jenn D.

Answer 9

根据我个人在更高级数据结构方面的经验，我认为你能做的最重要的事情是对树形数据结构的概念有很好的了解。如果你理解这个概念背后的基本机制，就会很容易实现符合你需求的解决方案。有很多描述该概念的优秀资料。在 "计算机程序设计艺术" 的 2.3 章节中，正是这个概念 "拯救" 了我。

- Ulrik Hørlyk Hjort