[Python-de] binaerer Baum in Python

Gerhard Häring haering_python at gmx.de
Sat Oct 27 02:58:22 EDT 2001


On Fri, Oct 26, 2001 at 02:49:44PM +0200, Gerhard Häring wrote:
> On Fri, Oct 26, 2001 at 02:21:41PM +0200, Albert Hermeling wrote:
> > Hallo,
> > 
> > bei meinen selbst Studien zum Thema Informatik bin ich jetzt bei den
> > binären Bäumen angekommen. Da ich der Auffassung bin das man am
> > besten lernt wenn man das gelernte auch gleich ausprobiert, versuche
> > ich seit drei Tagen sowass in Python zu realisieren. Bis jetzt habe
> > ich noch keine adäquate Lösung gefunden. Daher meine Frage: ist
> > sowas überhaupt in Python machbar? Wenn ja würde ich mich über ein
> > paar Tipps sehr freuen.
> > 
> > Bis jetzt habe habe ich es mit Listen und Dictionaries versucht.
> > musste das aber erfolglos aufgeben.
> 
> Ich würde das auf einer Node-Klasse aufbauen, die Attribute "left" und
> "right" hat, welche auf Instanzen von Node veweisen bzw. None für
> leer.
> 
> Dann brauchst du dir nur noch die Wurzel (root node) merken.
> 
> IIRC kann man dann weitergehen und die Node-Klasse mit Methoden zum
> Suchen und Einfügen erweitern.

Ok, ich hab ein bischen was hingekritzelt ;-) Dein eben erwähnter Ansatz
mit Listen ist zu kompliziert für meinen kleinen Kopf. Ich verwende da
lieber Klassen, um das große Problem in kleinere aufzuspalten:

Ok. Was ist ein Knoten im binären Baum? Er enthält einen Platzhalter für
die Daten, und *verweist* (=> Referenz) auf einen weiteren Konten links
und rechts. None, wenn kein solcher weiterer Knoten existiert. Das kann
man rel. einfach machen:

class Node:
    def __init__(self, data=None):
        self.data = data
        self.left = None
        self.right = None

    def __repr__(self):
        return "{%s, %i, %i}" % (str(self.data), id(self.left), id(self.right))


So, jetzt haben wir einen Knoten. Was noch abgeht, ist der eigentliche
binäre Baum, der solche Knoten enthält. Ich hab da auch schnell was
hingemalt, falls die Node-Klasse nicht genug Anregung ist:

WARNING, SPOILER AHEAD!!!

S
P
O
I
L
E
R
!

.
.
.
.
.
.
.
.
.
.
.
.
.
.


class BTree:
    def __init__(self):
        self.root = None

    def add(self, data):
        if self.root == None:
            self.root = Node(data)
        else:
            curnode = self.root
            lastnode = self.root
            while curnode != None:
                lastnode = curnode
                if data < curnode.data:
                    curnode = curnode.left
                    direction = -1      # links einfügen
                else:
                    curnode = curnode.right
                    direction = +1      # rechts einfügen
            if direction == -1:
                lastnode.left = Node(data)
            else:
                lastnode.right = Node(data)

    def _prchilds(self, node):
        if node != None:
            return "(%s, %s %s)" % (self._prchilds(node.left), node, self._prchilds(node.right))
        else:
            return "nil"

    def __repr__(self):
        return self._prchilds(self.root)

t = BTree()
t.add("Lukas")
t.add("Regina")
t.add("Gerhard")
t.add("Christian")
t.add("Magdalena")
print t

Gerhard
-- 
mail:   gerhard <at> bigfoot <dot> de       registered Linux user #64239
web:    http://www.cs.fhm.edu/~ifw00065/    OpenPGP public key id 86AB43C0
public key fingerprint: DEC1 1D02 5743 1159 CD20  A4B6 7B22 6575 86AB 43C0
reduce(lambda x,y:x+y,map(lambda x:chr(ord(x)^42),tuple('zS^BED\nX_FOY\x0b')))



More information about the Python-de mailing list