Поиск хорошей структуры данных дерева Python

Ответ 1

Сканируй свой собственный. Например, просто смоделируйте свое дерево как список списка. Вы должны подробно рассказать о своей конкретной потребности, прежде чем люди смогут дать лучшую рекомендацию.

В ответ на вопрос 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 поможет.

Ответ 2

Вы можете построить красивое дерево 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'})}) 

Для получения дополнительной информации посмотрите суть.

Ответ 3

Я нашел модуль, написанный Бреттом Алистером Кромкампом, который не был завершен. Я закончил его и опубликовал на github и переименовал его как treelib (original pyTree):

https://github.com/caesar0301/treelib

Пусть это поможет вам....

Ответ 4

Для дерева с упорядоченными детьми я обычно делал бы что-то вроде этого (хотя и немного менее общий, с учетом того, что я делаю):

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 или более современных потомков, если вы хотите, чтобы неупорядоченные дети обращались с помощью ключа.

Ответ 5

Возможно, стоит написать собственную обертку дерева на основе ациклического ориентированного графа, используя библиотеку networkx.

Ответ 6

Еще одна хорошая и простая в использовании реализация деревьев в Python - pyTree: https://github.com/caesar0301/pyTree

pyTree также предоставляет возможность визуализации дерева:

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

Ответ 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)))

Ответ 8

Основываясь на ответе, приведенном выше, с единственным деревом Tree, использующим defaultdict, вы можете сделать его классом. Это позволит вам установить значения по умолчанию в конструкторе и использовать его другими способами.

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

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

В этом примере вы можете сделать обратную ссылку, чтобы каждый node мог ссылаться на своего родителя в дереве.

>>> 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__ в дереве классов, чтобы при переназначении родителя он удалял его как дочерний элемент из этого родителя. Много классных вещей с этим рисунком.

Ответ 9

Может ли BTrees помочь? Они являются частью кода базы данных Zope. Загрузка всего пакета ZODB немного завышена, но я надеюсь, что модуль BTrees будет, по крайней мере, несколько разъединяемым.

Ответ 10

Я думаю, по собственному опыту по проблемам с более сложными структурами данных, что самое главное, что вы можете здесь сделать, - это получить хорошее знание общей концепции tress как структур данных. Если вы понимаете базовый механизм концепции, будет довольно легко реализовать решение, соответствующее вашей проблеме. Существует много хороших источников, описывающих концепцию. То, что "спасло" меня много лет назад по этой конкретной проблеме, было в разделе 2.3 "Искусство компьютерного программирования".