Szukam dobrej struktury danych Python Tree [zamknięte]

Szukam dobrej klasy struktury danych Tree. Natknąłem się na ten pakiet , ale ponieważ jestem stosunkowo nowy w Pythonie (nie programowaniu), nie wiem, czy są tam lepsze.

Chciałbym usłyszeć od Pythonistas tutaj - czy masz ulubiony skrypt drzewa, z którego regularnie korzystasz i który poleciłbyś?

[Edytować]

Aby wyjaśnić, przez „Drzewo” mam na myśli proste, nieuporządkowane drzewo (Hmm, to trochę rekurencyjna definicja - ale miejmy nadzieję, że to trochę wyjaśnia). Jeśli chodzi o to, do czego potrzebuję drzewa (np. Przypadek użycia). Czytam dane drzewa z płaskiego pliku i muszę zbudować drzewo z danych i przejść przez wszystkie węzły w drzewie.

Skręć swój własny. Na przykład po prostu zamodeluj swoje drzewo jako listę list. Powinieneś szczegółowo opisać swoją konkretną potrzebę, zanim ludzie będą mogli przedstawić lepsze rekomendacje.

W odpowiedzi na pytanie HelloGoodbye, oto przykładowy kod do iteracji drzewa.

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

Jednym z haczyków jest to, że rekurencyjna implementacja to O (n log n). Działa dobrze na wszystkich drzewach, z którymi mam do czynienia. Może pomógłby subgenerator w Pythonie 3.

Możesz zbudować ładne drzewo dykt w ten sposób:

import collections

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

Może to nie być dokładnie to, czego chcesz, ale jest całkiem przydatne! Wartości są zapisywane tylko w węzłach liści. Oto przykład, jak to działa:

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

Aby uzyskać więcej informacji, spójrz na sedno .

Znalazłem moduł napisany przez Bretta Alistaira Kromkampa, który nie został ukończony. Skończyłem to i upubliczniłem na githubie i zmieniłem jego nazwę na treelib(oryginałpyTree ):

https://github.com/caesar0301/treelib

Niech ci to pomoże ...

Opierając się na odpowiedzi podanej powyżej z pojedynczym drzewem liniowym przy użyciu defaultdict , możesz uczynić z niego klasę. Umożliwi to ustawienie wartości domyślnych w konstruktorze i zbudowanie na nich w inny sposób.

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

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

Ten przykład umożliwia utworzenie odniesienia wstecznego, tak aby każdy węzeł mógł odwoływać się do swojego rodzica w drzewie.

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

Następnie możesz nawet nadpisać __setattr__ w drzewie klas, aby podczas ponownego przypisywania rodzica usuwał go jako dziecko z tego rodzica. Wiele fajnych rzeczy z tym wzorem.

W przypadku drzewa z uporządkowanymi dziećmi zwykle robiłbym coś takiego (choć trochę mniej ogólne, dostosowane do tego, co robię):

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)

Możesz zrobić coś porównywalnego z a dictlub używając DictMixinlub bardziej nowoczesnych potomków, jeśli chcesz, aby nieuporządkowane dzieci miały dostęp za pomocą klucza.

Może warto napisać własne opakowanie drzewa oparte na acyklicznym ukierunkowanym grafie przy użyciu biblioteki networkx .

Oto coś, nad czym pracowałem.

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)

Użyj jako takich (liczby użyte jako wartości przykładowe): t = Tree(1, Tree(2, Tree(4)), Tree(3, Tree(5)))

Czy BTrees pomoże? Są częścią kodu Zope Object Database. Pobieranie całego pakietu ZODB to trochę przesada, ale mam nadzieję, że moduł BTrees byłby przynajmniej w pewnym stopniu rozdzielalny.

Myślę, że na podstawie własnego doświadczenia z problemami z bardziej zaawansowanymi strukturami danych najważniejszą rzeczą, jaką możesz tutaj zrobić, jest zdobycie dobrej wiedzy na temat ogólnej koncepcji warkocza jako struktur danych. Jeśli rozumiesz podstawowy mechanizm kryjący się za tą koncepcją, wdrożenie rozwiązania pasującego do Twojego problemu będzie dość łatwe. Istnieje wiele dobrych źródeł opisujących tę koncepcję. To, co „uratowało” mnie lata temu w tym konkretnym problemie, to sekcja 2.3 w „Sztuce programowania komputerowego”.