[Python-de] Kleine Aufgabe, große Wirkung

Fritz Cizmarov fritz at sol.at
Mon Apr 7 15:22:03 EDT 2003


Hallo Christian,

----------------------------------------------------------------
Am Sun, 06 Apr 2003 05:50:15 +0200
Schrieb Christian Tismer <tismer at tismer.com>:


> Also, jetzt geht's los: Gegeben ist ein unsortierter Baum.
> Den sollt Ihr "breadth-first" durchsuchen, linear, also es ist
> gar kein Such-Problem, einfach nur eine Frage der richtigen
> Reihenfolge. Die Knoten des Baums sehen beispielsweise so aus:
> 
>              1
>      2               3
>   4      5       6       7
> 8 9   10 11   12 13   14 15
> 
> Was man tun soll, ist, diese Knoten in der durch die Zahlen
> angegebenen Reihenfolge zu durchsuchen. Der Vorschlag ist,
> eine Testfunktion zu übergeben, welche versucht, den richtigen
> Knoten zurückzugeben. Ich empfehle, ein print-Statement
> einzubauen, welches verifiziert, daß Ihr wirklich in der
> vorgegebenen Reihenfolge sucht.
> 
> Der Einfachheit halber gebe ich hier einen Test-Baum vor, der
> trivialerweise die Knotennummern in dieser Reihenfolge
> enthält. Das ist zwar nicht der generelle Fall, aber für das
> Beispiel völlig ausreichend.
> 
> Hier der Beispiel-Baum: [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]]]]
> 
> Jetzt bin ich wirklich gespannt, ob die Deutsche
> Informatik-Grundausbildung effektiver ist als die Amerikanische.

also hier sehe ich schon mal ein grundlegendes Problem, warum den Baum
als verschachtelte Liste darstellen. Wenn schon Baum, dann aus einer
eigenen Node Klasse.

Beispiel

class Node():

    def __init__(self, value, left = None, right = None):
        self.value = value
        self.left = left
        self.right = right

    def search(self, value):
        if value < self.value:
            return self.left and search(self.left)
        elif value > self.value:
            return self.right and search(self.right)
        else:
            return self.value

    ....


Die eigentliche Lösung um den richtigen Node zu finden ist dann
praktisch nur noch ein Aufruf von search, auf den Wurzelknoten. Wie Du
siehst, hat der dann nur noch 7 Zeilen. Wenn aber die Einträge einfach
in eine Liste gegeben werden, so ist das sicher die effizienteste
Methode, da dann direkt mit den Listenmethoden gearbeitet werden kann
und die suche mit einem Aufruf erledigt ist.


Gruß

Fritz




More information about the Python-de mailing list