9

PROBLEMA

Estou precisando criar uma estrutura similar com a estrutura de diretórios a partir de uma lista de objetos semelhante à abaixo:

folders = []

folders.append(Folder(id=0, title='_ROOT', parent_id=-1000)
folders.append(Folder(id=1, title='A', parent_id=0))
folders.append(Folder(id=2, title='D', parent_id=3))
folders.append(Folder(id=3, title='B', parent_id=0))
folders.append(Folder(id=4, title='C', parent_id=1))
folders.append(Folder(id=5, title='E', parent_id=4))

Uma vez que não tenho ideia de qual será a profundidade desta estrutura, acredito que recursividade seja a solução.

Meu código

def get_folder_tree(folders):
    result = []
    for folder in folders:
        result.append(folder)
        result.extend(list(filter(lambda x: x.parent_id == folder.id, folders)))
    return result

Resultado atual

[<Folder: _ROOT>, <Folder: A>, <Folder: B>, <Folder: A>, <Folder: C>, <Folder: D>, <Folder: B>, <Folder: D>, <Folder: C>, <Folder: E>, <Folder: E>]

Resultado esperado

Alguma estrutura (dicionário ou árvore talvez) ou mesmo a impressão da estrutura conforme abaixo:

_ROOT
  A
    C
      E
  B
    D

2 Respostas 2

6

Se quer uma estrutura hierárquica, então uma lista contendo todos os objetos não é uma boa opção.

Uma alternativa seria cada Folder ter uma lista contendo apenas os seus filhos diretos. Usando o seu exemplo, o Folder _ROOT teria uma lista de filhos contendo apenas "A" e "B". Já o Folder "A" teria uma lista contendo apenas "C", que por sua vez teria uma lista contendo apenas "E", e por fim "B" teria uma lista contendo apenas "D".

Ou seja, adicione esta lista de filhos na sua classe Folder:

class Folder:
    def __init__(self, id, title, parent_id):
        self.id = id
        self.title = title
        self.parent_id = parent_id
        self.children = [] # lista de filhos, começa vazia

Se a ideia é partir da lista que você tem, então você percorre ela e para cada elemento verifica quem é o pai, e adiciona na lista de filhos deste:

def build_tree(folders):
    root = None
    for folder in folders:
        if folder.parent_id < 0: # assumindo que o root tem parent_id negativo
            root = folder
        else: # procura o pai deste folder, e atualiza a lista de filhos deste
            parent = next(filter(lambda f: f.id == folder.parent_id, folders))
            parent.children.append(folder)
    return root # retorna o nó raiz

Estou assumindo que o Folder raiz é o que tem parent_id negativo, e que só terá um. Para os demais, eu procuro pelo pai e adiciono o folder atual na lista de filhos do pai.

Claro que uma forma melhor seria poder passar a lista de filhos no próprio construtor, ou criar um método para adicionar. Mas se a ideia é construir a partir da lista, teria que ser assim (até daria para construir um dicionário que mapeia cada id com o respectivo Folder, assim não precisaria usar filter).

Também estou assumindo que filter sempre encontrará o id em questão, ou seja, não estou validando a estrutura. Você pode incluir esta verificação, bastando checar se next lança um StopIteration, por exemplo.

Depois, tendo o folder raiz, podemos fazer uma função recursiva que imprime toda a estrutura a partir dele:

def print_tree(folder, indent=''):
    print(f'{indent}{folder.title}')
    for child in folder.children:
        print_tree(child, indent + '  ')

Ou seja, primeiro imprime o Folder atual e depois imprime os seus filhos (adicionando espaços no início para ficar indentado). Testando:

folders = []
folders.append(Folder(id=0, title='_ROOT', parent_id=-1000))
folders.append(Folder(id=1, title='A', parent_id=0))
folders.append(Folder(id=2, title='D', parent_id=3))
folders.append(Folder(id=3, title='B', parent_id=0))
folders.append(Folder(id=4, title='C', parent_id=1))
folders.append(Folder(id=5, title='E', parent_id=4))

root = build_tree(folders)
print_tree(root)

Saída:

_ROOT
  A
    C
      E
  B
    D

Solução - na minha opinião - melhor

Como já dito acima, uma forma que considero melhor seria cada Folder poder ser criado já com seus filhos, além de ter um método para adicionar um novo filho:

class Folder:
    def __init__(self, id, title, parent_id=None, children=None):
        self.id = id
        self.title = title
        self.parent_id = parent_id
        self.children = []
        if children is not None:
            for child in children:
                self.add_child(child)

    # adiciona "child" na lista de filhos, e atualiza o parent_id deste
    def add_child(self, child):
        self.children.append(child)
        child.parent_id = self.id

No construtor eu optei por adicionar os filhos um a um usando o método add_child, pois ele já trata da lógica de atualizar o parent_id de cada filho (assim eu reaproveito esta lógica, em vez de duplicá-la no construtor).

Desta forma, eu elimino a necessidade de usar a lista (e consequentemente, também não preciso mais da função build_tree):

c = Folder(id=4, title='C', children=[Folder(id=5, title='E')])
a = Folder(id=1, title='A', children=[c])
b = Folder(id=3, title='B', children=[Folder(id=2, title='D')])
root = Folder(id=0, title='_ROOT', parent_id=-1000, children=[a, b])

print_tree(root)

# adicionar novos folders na estrutura fica mais fácil do que usando a lista
a.add_child(Folder(id=6, title='F'))
root.add_child(Folder(id=7, title='G', children=[Folder(id=8, title='H')]))
print_tree(root)

Repare que assim fica mais simples adicionar novos folders na estrutura. Usando a lista, você teria que chamar build_tree novamente (ou então fazer um build_tree_parcial, que verifica quais folders precisariam ser atualizados), ou seja, é mais uma prova de que a lista com todos os folders não é a estrutura mais adequada. E usar a estrutura de dados correta é meio caminho andado para um código melhor.

A saída do código acima é:

_ROOT
  A
    C
      E
  B
    D
_ROOT
  A
    C
      E
    F
  B
    D
  G
    H

Se ainda sim você quiser uma lista com todos os folders (sem se preocupar muito com a hierarquia), é possível obtê-la a partir do folder raiz:

# generator que obtém todos os folders a partir de um folder inicial
def get_all_folders(initial_folder):
    yield initial_folder
    for child in initial_folder.children:
        yield from get_all_folders(child)

# cria uma lista com todos
todos = list(get_all_folders(root))

# se eu só quero percorrer todos, não preciso criar uma lista
for folder in get_all_folders(root):
    # faz algo com o folder

Enfim, uma vez tendo a estrutura correta (cada folder contém uma lista dos filhos), é possível manipulá-la da maneira que quiser, e de forma bem mais simples do que se usasse uma lista com todos os folders.


Considerações finais

Só para constar, se fosse para continuar usando a lista, você teria que fazer algo do tipo:

def print_folders(folders, indent='', current_id=0):
    current = next(filter(lambda f: f.id == current_id, folders))
    print(f'{indent}{current.title}')
    for child in filter(lambda f: f.parent_id == current.id, folders):
        print_folders(folders, indent + '  ', child.id)

print_folders(folders)

A ideia é a mesma da função print_tree: começo na raiz e depois vou buscando os filhos dela (e faço chamadas recursivas para pegar os netos, bisnetos, etc). Mas veja que, como os folders só tem a informação de quem é o pai, eu preciso percorrer a lista toda hora, buscando os elementos que tem determinado parent_id. Isso é extremamente ineficiente, pois percorre a lista várias vezes (tendo uma lista de filhos, como feito anteriormente, pode até "gastar um pouco mais de espaço", mas o ganho em tempo acaba compensando, na minha opinião, pois assim eu não preciso percorrer todos os folders toda hora).

Mas e se você quisesse uma lista que, além de ter os folders, também tem a informação sobre o seu respectivo nível na hierarquia, então uma alternativa seria criar uma lista de tuplas (onde cada tupla tem o folder e seu nível):

def build_tree(folders, tree, level=0, current_id=0):
    current = next(filter(lambda f: f.id == current_id, folders))
    tree.append((current, level)) # folder e seu respectivo nível na árvore
    for child in filter(lambda f: f.parent_id == current.id, folders):
        build_tree(folders, tree, level + 1, child.id)

tree = []
build_tree(folders, tree)
for folder, level in tree:
    print(f'{"  " * level}{folder.title}')

Mas ainda sim tem o mesmo problema da ineficiência de percorrer a lista várias vezes. No fim, ainda prefiro as soluções anteriores (cada folder tem uma lista dos filhos), que não só são mais eficientes, como também são semanticamente mais corretas (já que a estrutura representa melhor como os dados são organizados de fato: como uma árvore/hierarquia).

5

Também é possível representar e manipular uma arvore com o auxilio do módulo treelib.

No manual são descritas algumas das características do módulo:

O treelib foi criado para fornecer uma implementação eficiente da estrutura de dados em árvore em Python.
As principais características do treelib incluem:

  • Operação eficiente de pesquisa de nó, O(1).
  • Suporta operações de árvore comuns, como travessia, inserção, exclusão, movimentação de nó, cópia superficial/profunda, corte de subárvore etc...
  • Suporta carga útil de dados definida pelo usuário para acelerar a construção de seu modelo.
  • Exibição bonita da árvore com dump de texto/json para exibição e análise offline.
  • Compatíbilidade com Python 2 e 3.

Para criar uma árvore use constructor treelib.tree.Tree(). Para para criar e adicionar nós filhos use o método treelib.tree.Tree.create_node() onde os parâmetros são:

  • tag : Um rótulo para o nó.
  • identifier: O identificador do nó dentro da hierarquia.
  • parent: O identificador do nó ancestral.
  • data: Um dado definido pelo usuário armazenado no nó.

O exemplo da pergunta ficaria:

from treelib import Node, Tree

folders = Tree()
folders.create_node('_ROOT',0)
folders.create_node('A', 1, 0)
folders.create_node('B', 3, 0)     #Note que foi modificada a ordem de inserção dos nós...
folders.create_node('D', 2, 3)     #...pois só é possível inserir um descendente a um nó já existente.
folders.create_node('C', 4, 1)
folders.create_node('E', 5, 4)

print(folders)

Cujo a saída:

_ROOT
├── A
│   └── C
│       └── E
└── B
    └── D

Teste o exemplo no Repl.it

2
  • 1
    A solução apresentada mereceu o upvote, porém, como não tenho como controlar a criação da lista que recebo, esta não atende ao caso específico. Mas o Tree() ficará na manga. Commented 28/09/2021 às 16:44
  • 1
    Eu entendi, e ainda bem frisei no exemplo a necessidade da mudança de ordem de inserção dos nós. Commented 28/09/2021 às 16:55

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .