[Python-de] Bäume....

Uwe Schmitt schmitt at num.uni-sb.de
Mon Okt 13 15:59:16 CEST 2003


::
:: Hallo zusammen,
::
:: ich braeuchte etwas Nachhilfe im Erzeugen von "Baeumen"
:: Als Bsp. habe ich die PID, PPID in eine Liste gepackt und
:: würde das ganze jetzt gerne als richtigen Baum (am besten noch mit Klassen)
:: aufbauen:
::
::
:: a)
::
:: so habe ich das bis jetzt rekursiv erledigt...:
::
::
:: #!/usr/local/bin/python
:: import string, sys, re, time
::
:: def getchilds(id):
::    for child,parent in id_dic.items():
::       if parent == id:
::          mynode = node(parent,id)
::          idlist.append(child)
::          getchilds(child)
::       mynode = node(parent)
::    return idlist
::

Habe ich dich richtig verstanden: du willst nicht nur die unmittelbaren
Kinder, sondern auch deren Kinder usw....
Ein dictionary ist dann gut, wenn die meiste Zeit mit Zugriffen
child->parent gearbeitet wird. In Python einen Baum zu programmieren
kann Sinn machen, ist aber meist nicht nötig. Dein Problem könnte
man auch wie folgt lösen:

   # list with entries (child, parent):
   li = [(2,1), (3,2), (4,2), (5,1), (6,5), (7,5), (8,5), (9,8)]

   # build reverse dictionary: parent -> list of childs:
   di = {}
   for child, parent in li:
       di.setdefault(parent,[]).append(child)

   def  getallchilds(pa):
	if di.has_key(pa):
	   for ch in di[pa]:
	      	yield ch
			for ch2 in getallchilds(ch):
				yield ch2


   # test
   for i in range(1,10):
	print
	print "children of %d: " % i,
        for ch in getallchilds(i): print ch,
	print


Gruß, Uwe.