寻找良好的 Python Tree 数据结构

我正在寻找一个很好的树数据结构类。我遇到过 这个包裹，但是由于我对 Python (不是编程)相对较新，我不知道是否还有更好的。

我希望在这里听到 Python 的声音-你有一个你经常使用并推荐的最喜欢的树脚本吗？

[编辑]

为了澄清，“树”，我指的是一个简单的无序的树(嗯，这是一个递归定义-但是希望，这在一定程度上澄清了事情)。关于我需要树做什么(例如用例)。我正在从一个平面文件中读取树数据，我需要根据这些数据构建一棵树，并遍历树中的所有节点。

136838 次浏览
小开

It might be worth writing your own tree wrapper based on an acyclic directed graph using the networkx library.

小开
最佳答案

Roll your own. For example, just model your tree as list of list. You should detail your specific need before people can provide better recommendation.

In response to HelloGoodbye's question, this is a sample code to iterate a tree.

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

One catch is this recursive implementation is O(n log n). It works fine for all trees I have to deal with. Maybe the subgenerator in Python 3 would help.

小开

For a tree with ordered children, I'd usually do something kind of like this (though a little less generic, tailored to what I'm doing):

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)

You could do something comparable with a dict or using DictMixin or it's more modern descendants if you want unordered children accessed by key.

小开

Would BTrees help? They're part of the Zope Object Database code. Downloading the whole ZODB package is a bit of overkill, but I hope the BTrees module would be at least somewhat separable.

小开

I found a module written by Brett Alistair Kromkamp which was not completed. I finished it and make it public on github and renamed it as treelib (original pyTree):

https://github.com/caesar0301/treelib

May it help you....

小开

You can build a nice tree of dicts of dicts like this:

import collections


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

It might not be exactly what you want but it's quite useful! Values are saved only in the leaf nodes. Here is an example of how it works:

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

For more information take a look at the gist.

小开

Here's something I was working on.

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)

Use as such (numbers used as example values): t = Tree(1, Tree(2, Tree(4)), Tree(3, Tree(5)))

小开

I think, from my own experience on problems with more advanced data structures, that the most important thing you can do here, is to get a good knowledge on the general concept of tress as data structures. If you understand the basic mechanism behind the concept it will be quite easy to implement the solution that fits your problem. There are a lot of good sources out there describing the concept. What "saved" me years ago on this particular problem was section 2.3 in "The Art of Computer Programming".

小开

Building on the answer given above with the single line Tree using defaultdict, you can make it a class. This will allow you to set up defaults in a constructor and build on it in other ways.

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


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

This example allows you to make a back reference so that each node can refer to its parent in the tree.

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

Next, you could even override __setattr__ on class Tree so that when reassigning the parent, it removes it as a child from that parent. Lots of cool stuff with this pattern.


提交答案