¿Cuál es la forma más eficiente de atravesar un árbol en Python?

Question

Suponiendo que haya una lista de objetos que tienen los siguientes campos

padre

valor

y esto define una estructura de árbol, similar a un árbol de directorios.

Quiero atravesar la lista de forma anticipada. ¿Cuál es la forma más eficiente?

Normalmente, en otros idiomas (más imperativos) iteraría los valores, buscando los que no tienen padres, luego, para cada uno, iterando de nuevo para cada objeto cuyo padre es el que estoy viendo actualmente, etc. pero, ¿hay una forma más inteligente de hacer esto en Python?

Answer 1

Me gustaría en primer lugar crear una estructura de datos más adecuada - capturar el enlace de un padre a sus hijos:

children = {} 
for obj in tree: 
    children.setdefault(obj.parent, []).append(obj) 

def preorder(root, children): 
    yield root.value 
    for child in children.get(root, []): 
     for value in preorder(child, children): 
      yield value 

for root in children[None]: 
    for value in preorder(root, children): 
     print value 

También es posible usar collections.defaultdict aquí.