Procurando por uma boa estrutura de dados Python Tree [fechado]

92

Estou procurando uma boa classe de estrutura de dados Tree. Eu encontrei este pacote , mas como sou relativamente novo em Python (não em programação), não sei se existe algum melhor por aí.

Gostaria de ouvir os Pythonistas aqui - você tem um script de árvore favorito que usa regularmente e recomendaria?

[Editar]

Para esclarecer, por 'Árvore', quero dizer uma árvore desordenada simples (Hmm, essa é uma definição um pouco recursiva - mas espero que isso esclareça as coisas um pouco). Em relação ao que eu preciso da árvore (ou seja, caso de uso). Estou lendo dados de árvore de um arquivo simples e preciso construir uma árvore a partir dos dados e percorrer todos os nós da árvore.

morfeo
fonte
Pelo menos uma duplicata tripla ... stackoverflow.com/questions/2482602/… bem como stackoverflow.com/questions/2358045/…
eric
1
Enquanto isso, há uma estrutura de dados em árvore simples, leve e extensível: anytree.readthedocs.io/en/latest
c0fec0de

Respostas:

38

Faça o seu próprio. Por exemplo, apenas modele sua árvore como uma lista de lista. Você deve detalhar sua necessidade específica antes que as pessoas possam fornecer recomendações melhores.

Em resposta à pergunta de HelloGoodbye, este é um código de amostra para iterar uma árvore.

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

Um problema é que a implementação recursiva é O (n log n). Funciona bem para todas as árvores com as quais tenho que lidar. Talvez o subgerador em Python 3 ajude.

Wai Yip Tung
fonte
Como você faz um loop sobre todos os elementos dessa árvore de uma forma 'pítônica'?
HelloGoodbye
Normalmente, você itera uma árvore usando DFS ou BFS. Eu costumo implementar um gerador usando DFS como def walk (tree): ...
Wai Yip Tung
1
O que é DFS e BFS? Essas siglas são novas para mim.
HelloGoodbye
1
Adicionado um código de amostra para DFS.
Wai Yip Tung
1
Pesquisa em profundidade significa que os filhos de um nó são visitados antes de seus irmãos. então, se você tiver `[A, [B, [C, D]], [E, [F, G]]]`, então, supondo que você visite B antes de E, você também visitará C e D antes de E. Largura- primeira pesquisa significa que todos os nós no mesmo nível são visitados antes de qualquer um de seus filhos, então B e E seriam visitados antes de qualquer um de C, D, F ou G.
Mark Reed
76

Você pode construir uma bela árvore de dictos de ditos como esta:

import collections

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

Pode não ser exatamente o que você deseja, mas é bastante útil! Os valores são salvos apenas nos nós folha. Aqui está um exemplo de como funciona:

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

Para obter mais informações, dê uma olhada na essência .

Stefan
fonte
1
Uau, usar defaultdict é uma ideia brilhante!
laike9m
Ótimo e eu sempre uso try, exceto com setters.
Jimmy Kane
5
uma desvantagem é que é muito complicado adicionar métodos relacionados à manipulação de árvores. também está no wiki e é chamado de autovivificação: en.wikipedia.org/wiki/Autovivification#Python
denfromufa
41

Encontrei um módulo escrito por Brett Alistair Kromkamp que não foi concluído. Terminei, tornei público no github e renomeei como treelib(original pyTree):

https://github.com/caesar0301/treelib

Que te ajude ....

caesar0301
fonte
5
licença é GPL, que pena
denfromufa
12
Essa licença foi concedida quando eu nem sabia o que significava uma licença. Eu sei que é um módulo simples, mas útil. Desde a versão 1.3.0, eu o redistribuo sob a Licença Apache. Agora você pode usá-lo onde precisar, com a declamação dos direitos autorais originais.
caesar0301
9

Com base na resposta dada acima com a Árvore de linha única usando defaultdict , você pode torná-la uma classe. Isso permitirá que você configure padrões em um construtor e desenvolva de outras maneiras.

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

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

Este exemplo permite que você faça uma referência anterior para que cada nó possa se referir a seu pai na árvore.

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

Em seguida, você pode até mesmo sobrescrever __setattr__ na classe Tree para que, ao reatribuir o pai, ele o remova como filho desse pai. Muitas coisas legais com esse padrão.

Sandy Chapman
fonte
O pai está quebrado para t [0] [1] [2] no exemplo acima. AttributeError: objeto 'int' não possui atributo 'pai'
MatthieuBizien
@oao Isso não está quebrado. Você está especificando t [0] [1] [2] = 3. Portanto, t [0] [1] [2] não será um tipo de dicionário padrão, mas um tipo de número (como defaultdict é usado para fazer padrões para elementos ausentes). Se você quiser que seja um padrão, você precisa usar t [0] [1] [2] sem a atribuição.
Sandy Chapman
7

Para uma árvore com filhos ordenados, eu normalmente faria algo mais ou menos assim (embora um pouco menos genérico, adaptado ao que estou fazendo):

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)

Você poderia fazer algo comparável com a dictou usando DictMixinou seus descendentes mais modernos se quiser que os filhos não ordenados sejam acessados ​​por chave.

Matt Anderson
fonte
7

Pode valer a pena escrever seu próprio envoltório de árvore baseado em um gráfico direcionado acíclico usando a biblioteca networkx .

Andrew Walker
fonte
5

Outra implementação boa e fácil de usar de árvores em Python é pyTree: https://github.com/caesar0301/pyTree

pyTree também fornece a possibilidade de visualizar a árvore:

Harry[harry]
|___ Jane[jane]
|    |___ Diane[diane]
|         |___ George[george]
|              |___ Jill[jill]
|         |___ Mary[mary]
|    |___ Mark[mark]
|___ Bill[bill]
aronadaal
fonte
2
Uma vantagem para tentar visualizar a árvore, embora a renderização fosse horrível.
HelloGoodbye
1
Duplicado da resposta já existente de casear0301 .
Jean-François Corbett
4

Aqui está algo em que eu estava trabalhando.

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 como tal (números usados ​​como valores de exemplo): t = Tree(1, Tree(2, Tree(4)), Tree(3, Tree(5)))

Aaron Robson
fonte
3

O BTrees ajudaria? Eles são parte do código do banco de dados de objetos do Zope. Baixar o pacote ZODB inteiro é um pouco exagerado, mas espero que o módulo BTrees seja pelo menos um pouco separável.

Jenn D.
fonte
2

Eu acho que, por experiência própria em problemas com estruturas de dados mais avançadas, a coisa mais importante que você pode fazer aqui é obter um bom conhecimento sobre o conceito geral de árvores como estruturas de dados. Se você entender o mecanismo básico por trás do conceito, será muito fácil implementar a solução que se adapta ao seu problema. Existem muitas fontes boas por aí que descrevem o conceito. O que me "salvou" anos atrás neste problema específico foi a seção 2.3 em "A Arte da Programação de Computador".

U. Hjort
fonte