Alla ricerca di una buona struttura dati Python Tree



Answers

Puoi costruire un bel albero di dictte di dict come questo:

import collections

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

Potrebbe non essere esattamente quello che vuoi ma è abbastanza utile! I valori vengono salvati solo nei nodi foglia. Ecco un esempio di come funziona:

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

Per maggiori informazioni dai un'occhiata al succo .

Question

Sto cercando una buona struttura della struttura dati Tree. Ho trovato questo pacchetto , ma dato che sono relativamente nuovo a Python (non alla programmazione), non so se ce ne sono di migliori là fuori.

Mi piacerebbe sapere da Pythonistas qui - hai uno script di albero preferito che usi regolarmente e che consiglieresti?

[Modificare]

Per chiarire, con 'Albero', intendo un albero non ordinato semplice (Hmm, questo è un po 'una definizione ricorsiva - ma si spera che chiarisca un po' le cose). Per quanto riguarda ciò di cui ho bisogno per l'albero (cioè caso d'uso). Sto leggendo i dati dell'albero da un file piatto e ho bisogno di costruire un albero dai dati e attraversare tutti i nodi dell'albero.




Penso che, dalla mia esperienza sui problemi con strutture di dati più avanzate, che la cosa più importante che puoi fare qui, sia ottenere una buona conoscenza del concetto generale di alberi come strutture di dati. Se capisci il meccanismo di base dietro il concetto, sarà abbastanza semplice implementare la soluzione adatta al tuo problema. Ci sono molte buone fonti là fuori che descrivono il concetto. Quello che mi ha "salvato" anni fa su questo particolare problema era la sezione 2.3 in "L'arte della programmazione informatica".




Un'altra implementazione buona e facile da usare degli alberi in Python è pyTree: https://github.com/caesar0301/pyTree

pyTree fornisce anche la possibilità di visualizzare l'albero:

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



Ecco qualcosa su cui stavo lavorando.

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)

Utilizzare come tale (numeri utilizzati come valori di esempio): t = Tree(1, Tree(2, Tree(4)), Tree(3, Tree(5)))




Per un albero con bambini ordinati, di solito faccio qualcosa di simile a questo (anche se un po 'meno generico, su misura per quello che sto facendo):

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)

Potresti fare qualcosa di paragonabile a un dict o usare DictMixin o discendenti più moderni se vuoi che i bambini non ordinati DictMixin per chiave.




Links