[Python-de] binaerer Baum in Python

Albert Hermeling Albert.Hermeling at t-online.de
Sat Oct 27 15:42:31 EDT 2001


Am Samstag, 27. Oktober 2001 01:58 schrieben Sie:
> 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.

> > 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, dann werde ich mit meinen großen Kopf ;-) mal versuchen ob ich Deine 
Lösung verstehe.

>
> 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:
Anders gesagt eine Variabel, Liste, oder was auch immer für die Daten und 
zwei Zeiger für die Nachfolge Knoten. 

> class Node:
>     def __init__(self, data=None):
>         self.data = data
>         self.left = None
>         self.right = None
Gut bis dahin komme ich noch mit.

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

Mit dieser Methode weist Du der Variabel (z. B.) und den Zeigern ihre Werte 
zu . Das ist mir auch noch klar.

So was jetzt kommt verstehe ich nicht. Trotz meines großen Kopfes ;-(( 

> class BTree:
>     def __init__(self):
>         self.root = None
Das ist soweit klar.
>
>     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)

Was ich nicht verstehe ist

1. Was meinst Du mit curnode und lastnode?

2.  Wo ist der Name des Referenzelementes gespeichert das auf den nächste 
Knoten zeigt?

3. musst Du den ganzen Baum durchsuchen um ein Element einzufügen oder zu 
finden?

Ich währe Dir dankbar wenn Du mir zu Deinem Listing noch ein paar Zeilen 
dazuschreiben könntest.

mfg

Albert



More information about the Python-de mailing list