Python'da bir ağacı hareket ettirmenin en etkili yolu nedir?

Question

Ben aşağıdaki alanları

değeri

ebeveyn ve bu bir dizin ağacına benzer bir ağaç yapısını tanımlar sahip nesnelerin bir listesi var varsayarsak.

Listeyi ön siparişte taşımak istiyorum. En verimli yol nedir?

Normalde, diğer (daha fazla zorlayıcı) dillerde, ebeveynleri olmayanları bulmak, sonra her biri için, şu anda bakmakta olduğum ve benzerleri olan her nesne için tekrar yineleme, değerleri yinelemek, ama bunu Python'da yapmanın daha akıllıca bir yolu var mı?

Answer 1

Ben ilk daha uygun veri yapısını yaratacak - onun çocuklarına bir ebeveynden bağlantıyı yakalayan:

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 

Ayrıca buradan collections.defaultdict kullanabilirsiniz.