Tree sortieren

[cullmann]

Servus alle zusammen,

mir hat nen freund die folgede aufgabe geschickt und gemeint das diese aufgabe sehr schön verdeutlich wie gut man mit python programmieren kann. Soweit so gut, jetzt habe ich die Aufgabe gelöst, aber natürlich ist mein kumpel net da, sonder im urlaub und kann mir seine "super" lösung net schicken. Deswegen wollte ich euch mal fragen wie ne vernünftige lösung aussehen würde.

Code: Alles auswählen

# Tree
#              1
#      2              3
#  4      5       6       7
# 8 9   10 11   12 13   14 15

# [value, child1, child2]



t = [1,
          [2,
               [4,
                    [8, None, None],
                    [9, None, None]],
               [5,
                    [10, None, None],
                    [11, None, None]]],
          [3,
               [6,
                    [12, None, None],
                    [13, None, None]],
               [7,
                    [14, None, None],
                    [15, None, None]]]]


# Meine loesung:
myList = []

def pt(level):
    if myList == []:
        myList.append(level[0])
	
    for i in range(1, 3):
        myList.append(level[i][0])
        print level[i][0]
        if level[i][1] != None:
            pt(level[i])

Also eigentlich sortiert ja pt den baum nicht sonder ließt nur die values aus, ich führen aus myList dann nochmal ein .sort aus.

Würde mich über ne antwort freuen!

[Rebecca]

mir hat nen freund die folgede aufgabe geschickt

Was genau ist denn die Aufgabe?

[cullmann]

Verdammt, ich wußte doch das ich was vergessen habe.....

Also die Aufgabe besteht darin den Baum zu sortieren, also die Values der Knoten aufsteigend sortieren aber nicht als Baum dann abspeichern sondern einfach nur in ne liste.
Sorry

[EnTeQuAk]

Der Baum ist zwar irgentwie merkwürdig, aber die Lösung ist relativ einfach.

Ich hätte es so gemacht:

Code: Alles auswählen

In [29]: def flatten(items):
    ret = []
    for item in items:
        if isinstance(item, list):
            ret += flatten(item)
        else:
            ret.append(item)
    return ret
   ....: 

In [37]: tree
Out[37]: 
[1,
 [2,
  [4, [8, None, None], [9, None, None]],
  [5, [10, None, None], [11, None, None]]],
 [3,
  [6, [12, None, None], [13, None, None]],
  [7, [14, None, None], [15, None, None]]]]

In [38]: sorted(filter(None, flatten(tree)))
Out[38]: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]

Wobei man sich das`flatten` aufgrund der bekannten Datenstruktur mit einer List-Comprehension vermutlich sparen kann.

MfG EnTeQuAk

[audax]

Code: Alles auswählen

def flatten(items):
    ret = []
    for item in items:
        try:
            ret.extend(flatten(item))
        except TypeError:
            ret.append(item)
    return ret

Irgendwie eine...komische Aufgabe.

Als Aufruf dann:

Code: Alles auswählen

print sorted(filter(bool, flatten(t)))

Oder als generator:

Code: Alles auswählen

def flatten(items):
    for item in items:
        try:
            for i in flatten(item):
                yield i
        except TypeError:
            yield item

[Rebecca]

filter(None,...) oder filter(bool,...) wuerde auch Elemente mit dem Wert 0 wegschmeissen...

[audax]

Gnaah...du hast recht.

Code: Alles auswählen

print sorted(i for i in flatten(t) if isinstance(i, int))

[BlackJack]

Also ich finde es ja immer schön, wenn Schüler ihre Lehrer als Freunde ansehen. Dass die die Lösung von Hausaufgaben nicht rausrücken ist aber auch wirklich doof.

[EyDu]

Hey, aber cullmann war wenigstens bei seiner Geschichte kreativ

[cullmann]

super alles voller spazzvögel hier
Das war keine verdammte aufgabe von nem Lehr du vogel, hab jetzt auch raus bekommen wo die aufgabe "ursprünglich" herkommt:
http://osdir.com/ml/python.general.germ ... 00059.html


Aber hey, hauptsache was gesagt.....

[audax]

Pf...paulst auch nich hier rum, nachdem dir geholfen wurde? Ich glaube es hackt

[querdenker]

Immerhin hat cullmann gleich bei der Eröffnung Code dabei gehabt.

[Leonidas]

Das war keine verdammte aufgabe von nem Lehr du vogel

Vogel? Das war doch das Signalwort "ich bin ein Troll, schließe meinen Thread"