Die letzten 10 Beiträge |
John D Dorian |
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 ^^ |
Pedder |
RWTH laesst gruessen
|
Karlito |
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 |
John D Dorian |
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 ^^ |
Karlito |
Dein compare müsste so gehen.
Bei inorder sind noch Fehler.
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
|
public int[] inorder(int n){
int[] a = new int[n];
int x = 0;
if(leftChild != null)
leftChild.inorder(); //Hier müsste noch mal die Anzahl rein
//Außerdem wäre es günstig zu schreiben
//this.leftChild, da sonst nimand weis
//dass es ein Member von Tree sein soll
a[x] = data; //Du kannst m.E. nicht
//einfach einem Arrayelement
//ein anderes Array zuweisen
x++;
if(rightChild != null)
rightChild.inorder();
//Hier fehlt dann wieder das Anfügen des Arrays von rightchild
return a;
}
|
|
Aber das grobe prinzip stimmt.
Bei dynamischen datentypen bräuchtest du die Anzahl nicht. Da könntest du sowas machen wie:
code: |
1:
2:
3:
4:
5:
6:
7:
8:
9:
|
Collection result = this.leftChild().inorder();
result.add(this.value);
result.append(this.rightChild().inOrder());
return result;
//Code nicht Korrekt! Da Enden des Baumes und erstellung der Collections fehlen
|
|
Is Geschmackssache... Wie sich das auf die Laufzeit auswirkt weis ich grad nicht... |
John D Dorian |
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;
} |
|
|
John D Dorian |
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 |
Karlito |
Hab grad deine Funktion noch mal gelesen.
Das haut so nicht hin. Du musst nen Baum übergeben und eine Liste generieren (wenn funktion nicht teil der Baum-Klasse). Das ist leider nicht so einfach wie du dir das da gemacht hast.
Wenn die funktion teil des Baumes ist, brauchst du eigentlich nichts übergeben sondern nur inorder ausrufen und die Listen vergleichen.
Ein Array kannst du m.E. auch nicht so einfach verwenden, da du was dynamisch wachsendes brauchst (LinkedList/ArrayList) oder du fügst die 2 Arrays für links und rechts mit deinem Wert zusammen.
VG,
Karlito |
Karlito |
Die In-Order Traversierung sollte wichtig sein, der Baum sonst nicht geordnet durchgegangen wird.
Suchbaumeigenschaft heißt, dass der Baum geordnet ist. D.h. links stehen immer die kleineren Werte als die Wurzel und rechts die größeren.
Und O(3n) = O(n). Bei der Komplexitätsbetrachtung lässt man so ziemlich alles mögliche weg, was keine Rolle spielt. Auch wenn 3n, bleibt das Verhalten linear. Leider bin ich noch ni fit genug auf dem Gebiet um dir ne formale Begründung geben zu können.
Deine Funktion müsste hinhauen (nach grobem überlesen). Und dein Aufruf auch.
@3FBN: Sorry, dass ich mich einfach reingehängt habe
VG,
Karlito |
John D Dorian |
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())? |
Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |