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.
Respostas:
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.
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.
fonte
Você pode construir uma bela árvore de dictos de ditos como esta:
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:
Para obter mais informações, dê uma olhada na essência .
fonte
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
(originalpyTree
):https://github.com/caesar0301/treelib
Que te ajude ....
fonte
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.
Este exemplo permite que você faça uma referência anterior para que cada nó possa se referir a seu pai na árvore.
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.
fonte
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):
Você poderia fazer algo comparável com a
dict
ou usandoDictMixin
ou seus descendentes mais modernos se quiser que os filhos não ordenados sejam acessados por chave.fonte
Pode valer a pena escrever seu próprio envoltório de árvore baseado em um gráfico direcionado acíclico usando a biblioteca networkx .
fonte
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:
fonte
Aqui está algo em que eu estava trabalhando.
Use como tal (números usados como valores de exemplo):
t = Tree(1, Tree(2, Tree(4)), Tree(3, Tree(5)))
fonte
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.
fonte
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".
fonte