Algorithmus zum vergleichen zweier Binärbäume |
John D Dorian unregistriert
|
|
Algorithmus zum vergleichen zweier Binärbäume |
|
Meine Frage:
Ich soll einen Algorithmus entwerfen der in O(n) testet, ob zwei Binärbäume mit n Elemente dieselben Elemente haben.
Ich geh mal davon aus dass die Reihenfolge in denen die Elemente im Baum sind egal ist.
Meine Ideen:
Ich schaffs irgendwie nur in O(n²), denn ich würde jeden Wert des ersten Baumes mit (höchstens) allen Werten des zweiten Baumes vergleichen.
Könnte mir jemand einen Hinweis geben wie man es in O(n) schafft?
|
|
25.04.2011 12:52 |
|
|
3FingerbreitNougat unregistriert
|
|
Zuerst solltest du prüfen ob die aktuellen Felder gleich sind.
Dann, ob links und rechts alles gleich ist.
Rekursion.
So würde ich es machen.
3FBN
|
|
25.04.2011 14:38 |
|
|
John D Dorian unregistriert
|
|
also wenn ich die aktuellen felder überprüfe und dann links und rechts, also so gesehen beide Bäume gleichzeitig durchsuche, dann müssen die gleichen Werte ja an derselben Stelle im Baum sein, oder?
und bei der traversierung, ist das wichtig dass es inorder ist oder könnte es theoretisch auch jede andere traversierung sein... aber da ist es doch das problem dass ich beide bäume erstmal in eine liste packen muss... meintest du mit "wichtig suchbaumeigenschaft" dass die liste die eiganschaft haben muss geordnet zu sein? weil wenn die liste nicht geordnet ist, geht das ja auch nur wenn die elemente an der gleichen stelle sind
gerade beim schreiben ist mir eingefallen das wenn ich beide bäume erst in eine geordnete liste packe und sie dann vergleiche es ja dann 3n wäre und ich meine mal gehört zu haben das man den faktor davor vernachlässigen kann, es also dann O(n) ist?
|
|
25.04.2011 17:04 |
|
|
John D Dorian unregistriert
|
|
sorry für Doppelpost, aber als unregistrierter User kann ich meinen Beitrag leider nicht editieren...
also ich habs mal so gemacht (in java, ungetestet, da ich im moment keine lust hab ne Baum-Klasse zu schreiben)
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
|
public int[] inorder(int n){
int[] a = new int[n];
int x = 0;
if(leftChild != null)
leftChild.inorder();
a[x] = data;
x++;
if(rightChild != null)
rightChild.inorder();
return a;
}
public boolean cmp(int[] a, int[] b){
for(int x = 0; x <= a.length x++){
if(a[x] != b[x])
return false
}
return true;
}
|
|
kann man das so machen? was müsste man dann in der main-klasse aufrufen? cmp(tree1.inorder(), tree2.inorder())?
|
|
25.04.2011 18:17 |
|
|
John D Dorian unregistriert
|
|
Wie meinste das mit baum übergeben... wenn ich tree1.inorder(anzahl der elemente) mach müsste das doch eig. gehen... und bei int[] a = new int[n] wird ja ein array erstellt das genug felder hat, also man muss ja eingeben wieviel man haben will, also wenn ein neues dazu kommt oder gelöscht wird (wenn du das meinst mit dynamisch wachsen) dann trägt man halt ne andere zahl ein (oder muss noch ne methode schreiben um die anzahl der elemente herauszufinden, aber das ist ja im mom nicht gefragt)
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
|
public boolean cmp(int[] a){
for(int x = 0; x <= a.length x++){
if(a[x] != b[x])
return false
}
return true;
}
|
|
so müsste es dann aber gehen mit tree1.cmp(tree2.inorder(anzahl der elemente)), oder?
wollt eig eh nur mal so schauen wie man das implementieren kann, wir müssen das glaub ich so gar nicht sondern nur sagen wie wir das machen würden und vll in Pseudo-Code hinschreiben
|
|
25.04.2011 20:29 |
|
|
John D Dorian unregistriert
|
|
damn wie ichs blöd find nicht editieren zu können, da ich dazu neige fehler zu machen -.-
meinte:
code: |
1:
2:
3:
4:
5:
6:
7:
|
public boolean cmp(int[] a){
for(int x = 0; x <= a.length x++){
if(a[x] != this.inorder(anzahl der elemente))
return false
}
return true;
} |
|
|
|
25.04.2011 20:34 |
|
|
John D Dorian unregistriert
|
|
achso ja die anzahl bei leftchild.inorder() hab ich vergessen
unter rightchild.inorder(int n) dann auch einfach nochmal
a[x] = data;
x++;
?
und data ist ja nur der wert den ich ins array einfüge und kein arrayelement
aber danke schön, dass du dir soviel zeit genommen hast ^^
|
|
25.04.2011 22:17 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
leftChild.inOrder() gibt dir doch ne Liste zurück. Da es nicht genau beschrieben ist was data sein soll, bin ich davon ausgegangen, dass es der Rückgabewert von leftChild.inOrder() sein soll.
Somit wäre es ja schon ein Array und du kannst es nicht einfach einem Arrayelement zuweisen...
Am besten du implementierst das mal durch und Probierst es mal aus. Sollte nicht zu lange dauern...
Zitat: |
aber danke schön, dass du dir soviel zeit genommen hast ^^ |
Gerne.
VG,
Karlito
|
|
25.04.2011 22:30 |
|
|
Pedder unregistriert
|
|
RWTH laesst gruessen
|
|
25.04.2011 22:57 |
|
|
John D Dorian unregistriert
|
|
grüße zurück, hoffe wir konnten dir auch helfen pedder ^^
und karlito wie gesagt, wir müssen es ja eig. gar nicht implementieren sondern nur den algorithmus angeben
wie gesagt danke nochmals für den hinweis auf inorder ^^
|
|
26.04.2011 10:53 |
|
|
|