binäre bäume < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 10:22 Do 21.06.2007 | | Autor: | AriR |
| Aufgabe | Erläutern Sie, wie man einen binären Suchbaum mit dem Schlüsseltyp int so in einen intArray
a umwandeln kann, dass man aus a den Suchbaum in der ursprünglichen Form rekonstruieren
kann. Geben sie Algorithmen für beide Richtungen an (Suchbaum <--> Array) und begründen Sie
Korrektheit und Laufzeit. |
hey leute,
ich dachte mir, da binäre bäume nicht eindeutig bestimmt sind, muss man die wurzel kennen um diese genau so wieder aus dem array erstellen zu können, wie sie ursprünlich aussahen.
dachte mir dann, dass man die wurzel in an der stelle 0 des arrays einspeichert und den rest einfach reihenweise rein angefangen mit dem kleinsten element (Also immer getMin() und removeMin() bis der baum leer ist)
danach könnte man wieder um den baum zu rekonstruieren einfach reihenweise die elemente aus dem array angefagen bei 0 wieder in den baum einfügen und es müsste der selbe baum wieder haurauskommen, den man ursprünglich hatte, da beide die selbe wurzel haben oder nicht?
mein problem ist jetzt, dass ich keine ahnung habe wie ich die wurzel aus der schnittstelle eines binären baums bekommen kann.
mir stehen nur folgende methoden zur verfügung:
// ******************PUBLIC OPERATIONS*********************
// void insert( x ) --> Insert x
// void remove( x ) --> Remove x
// void removeMin( ) --> Remove minimum item
// Comparable find( x ) --> Return item that matches x
// Comparable findMin( ) --> Return smallest item
// Comparable findMax( ) --> Return largest item
// boolean isEmpty( ) --> Return true if empty; else false
// void makeEmpty( ) --> Remove all items
wäre super, wenn mir einer von euch helfe könnte :)
Gruß ;)
|
|
| |
|
> Erläutern Sie, wie man einen binären Suchbaum mit dem
> Schlüsseltyp int so in einen intArray
> a umwandeln kann, dass man aus a den Suchbaum in der
> ursprünglichen Form rekonstruieren
> kann. Geben sie Algorithmen für beide Richtungen an
> (Suchbaum <--> Array) und begründen Sie
> Korrektheit und Laufzeit.
> hey leute,
>
> ich dachte mir, da binäre bäume nicht eindeutig bestimmt
> sind, muss man die wurzel kennen um diese genau so wieder
> aus dem array erstellen zu können, wie sie ursprünlich
> aussahen.
>
> dachte mir dann, dass man die wurzel in an der stelle 0 des
> arrays einspeichert und den rest einfach reihenweise rein
> angefangen mit dem kleinsten element (Also immer getMin()
> und removeMin() bis der baum leer ist)
>
> danach könnte man wieder um den baum zu rekonstruieren
> einfach reihenweise die elemente aus dem array angefagen
> bei 0 wieder in den baum einfügen und es müsste der selbe
> baum wieder haurauskommen, den man ursprünglich hatte, da
> beide die selbe wurzel haben oder nicht?
>
> mein problem ist jetzt, dass ich keine ahnung habe wie ich
> die wurzel aus der schnittstelle eines binären baums
> bekommen kann.
>
> mir stehen nur folgende methoden zur verfügung:
>
> // ******************PUBLIC
> OPERATIONS*********************
> // void insert( x ) --> Insert x
> // void remove( x ) --> Remove x
> // void removeMin( ) --> Remove minimum item
> // Comparable find( x ) --> Return item that matches x
> // Comparable findMin( ) --> Return smallest item
> // Comparable findMax( ) --> Return largest item
> // boolean isEmpty( ) --> Return true if empty; else
> false
> // void makeEmpty( ) --> Remove all items
>
>
> wäre super, wenn mir einer von euch helfe könnte :)
>
> Gruß ;)
mhm also ich kenn diese Beispiele nur mit sogenannter InOrder (IO)Reihenfolge und PreOrder (PO) Reihenfolge.
mal kurze erklärung dazu.
IO:
du fangst bei der wurzel an und gehst solange nach links bis du anstehst (=kleinstes element des Suchbaum) danach wird dieses ins array an die 1 Position geschrieben. dann gehst du eine ebene hinauf (zum Vater vom kleinsten) und schreibst den hinein ins array. danach schaust du ob dieser ein rechtes kind hat und schreibst es an die 3 stelle des arrays(falls vorhanden) ansonsten gehst du wieder eine ebene hinauf...
mal ein Bsp:
10
/ [mm] \
[/mm]
5 20
/ \ / [mm] \
[/mm]
1 7 15 25
IO ergibt : 1,5,7,10,15,20,25
PO geht vom prinzip her ähnlich vor, nur das sofort das element wo sie ist ins array schreibt
PO ergibt : 10,5,1,7,20,15,25
wenn du nun aus PO und IO den baum erstellen willst gehst du wie folgt vor : du läufst von i=1 bis PO.size alle elemente durch.
PO[1]=Wurzel des Baums
nun musst du dir aus der IO die position des Wertes von PO[1] suchen.
hier ist dies pos 4 => alles was in der IO links dieser Position steht gehört zum linken unterbaum alles was rechts davon ist zum rechten.
L W R
1,5,7 10 15,20,25
nun nimmst du PO[2] her da dies das element ist was links von der wurzel steht.
dies ist PO[2]=5 dadurch das du weisst das es links von der Wurzel ist musst du nur in L suchen
pos=2
dein baum schaut jetzt so aus 10
/
5
nun siehst du das 5 in der mitte ist und teilst wieder in L und R auf.
nun niummst du PO[3]=1 und hast das linke element von 5
PO[4]=7 ist das rechte elemet von 5
analog geht das für die rechte seite des baumes!
hoffe das hilft dir! Musst dir halt nur überlegen wie es mit deinen Funktionen aussieht die du zur verfügung hast!
LG
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 14:31 Do 21.06.2007 | | Autor: | AriR |
das ist ja so mehr oder weniger das problem..
ich bekomme mit den funktionen die wurzel nicht, auf jeden fall weiß ich nicht wie
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 14:54 Do 21.06.2007 | | Autor: | Schmon |
Hallo AriR
Das was devilofdeath da geschrieben hat ist auf jeden Fall richtig.
Wenn du die Preorder Reihenfolge des Baumes bekommst, dann
kannst du den Baum damit jeder Zeit wieder aufbauen.
Die Operationen welche dir zur Verfügung stehen helfen dabei allerdings nicht
sehr weit.
Die Wurzel allerdings dürfte kein Problem sein, denn die Variabel, in welcher der Baum gespeichert ist (wird wohl ein Pointer sein) zeigt (bei sinnvollen Implementierungen) immer auf die Wurzel, das heisst wenn du die Variabel dereferenzierst hast du deine Wurzel.
Wie du allerdings an den Rest kommen möchtest das versteh ich nicht ganz aber veilleicht hats dir ja schon geholfen.
Wäre nett ein kleines Feedback zu bekommen
Gruss Schmon
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 15:16 Do 21.06.2007 | | Autor: | AriR |
leider nicht, denn ich kann ja nicht in der implementierung des baums rumspielen sonder darf diese nur als schnittstelle betrachten, d.h. ich darf nur die oben genannten methoden dafür verweden :(
ich hab ka wie ich damit die wurzel bekomme oder ich muss einen ganz anderen weg gehen, aber auf die art weiß ich nur, wie ich einen äquivalten binärbaum bekomme und nicht exakt den selben
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 15:22 Di 26.06.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
