| Zeige Beiträge 1 bis 14 von 14 Treffern |
|
 Thema: Iterative Tiefensuche |
|
|
ok, vielen dank!
das mit dem arbeitsspeicher war mir nicht bewusst!
vielen dank für deine (erneute) hilfe! 
|
|
| Thema: Iterative Tiefensuche |
|
|
Kann mir jemand erklären, was bei der iterativen Tiefensuche genau passiert? Mir fällt es schwer, den Unterschied zur normalen Breitensuche zu erkennen.
Also bei der Tiefensuche geht man von einem Knoten aus einfach mal bis ganz in die Tiefe. Kommt dann wieder zurück und macht das Selbe beim nächsten Knoten.
Bei der Breitensuche geht man von der Wurzel zum linken und rechten Knoten. Dann geht man einen Knoten weiter, wieder zum linken und rechten (bzw eifach zu allen direkte Erreichbaren).
Und die iterative Tiefensuche soll ja ein Mix aus beiden sein. Und ich weiss, dass man zuerst die Höhe 1 absucht, dann die Höhe 2 etc.
Aber macht man das nicht eigentlich genau bei der Breitensuche?
Was ist genau der Vorteil zur Breitensuche?
Der Vorteil gegenüber der normalen Tiefensuche scheint mir klar, da man bei der normalen Tiefensuche jenachdem "unendlich" tief geht, und das Gesuchte lange nicht oder gar nie findet..
|
|
| Thema: Binärer Suchbaum in ArrayList einsortieren |
|
|
Aha! okay!
Also:
public ArrayList<T> createSortedList(BinarySearchTree<T> tree) {
return createSortedList(tree, new ArrayList<T>());
}
private ArrayList<T> createSortedList(BinarySearchTree<T> tree, ArrayList<T> list)
{
if (tree.left != null)
createSortedList(tree.left, list);
list.add(tree.thing);
if (tree.right != null)
createSortedList(tree.right, list);
return list;
}
Und das wärs, oder? =)
|
|
| Thema: Binärer Suchbaum in ArrayList einsortieren |
|
|
Ok, alles klar. :-)
Aber wenn ich meinen Baum in eine ArrayList wandeln würde, wie müsste ich da vorgehen? Da kann ich ja eben nicht deine add Methode verwenden, oder habe ich das Prinzip einfach noch nicht verstanden?
Weil die insert Methode soll so stehen bleiben und dann in einem nächsten Schritt die sortierte Liste ausgegeben werden.
|
|
| Thema: Binärer Suchbaum in ArrayList einsortieren |
|
|
Ok, aber eigentlich hätte ich die Werte vorher bereits in einen Baum eingefüllt. Mit einer insert-Methode.
Und von diesem Baum muss ich jetzt die ArrayListe zurückgeben. Dann wäre es ja falsch, wenn ich die Werte "nochmals" einfügen würde?
Meine Insert Methode würde etwa so ausehen:
public BinarySearchTree<T> insert(BinarySearchTree<T> tree, int key, T thing) {
if(tree==null)
return new BinarySearchTree<T>(key,thing);
if(tree.key==key)
tree.thing=thing;
if(key< tree.key)
tree.left=insert(tree.left, key,thing);
if(key> tree.key)
tree.right=insert(tree.right, key, thing);
return tree;
}
(Stimmt das so überhaupt?)
|
|
| Thema: Binärer Suchbaum in ArrayList einsortieren |
|
|
Ok, danke!
Aber wenn ich jetzt wirklich nur eine Liste ausgeben müsste, ohne zusätzliche weitere Methode (wie hier add).
Wie bringe ich dann die Werte auf die Liste?
|
|
| Thema: Binärer Suchbaum in ArrayList einsortieren |
|
|
Ach so, aber demfall erstelle ich so einen Baum?
Ich möchte ja eigentlich von einem gegebenen Baum eine sortierte ArrayListe erstellen. Für das muss ich ja keinen neuen Knoten machen? Oder?
|
|
| Thema: Binärer Suchbaum in ArrayList einsortieren |
|
|
Hallo eulerscheZahl
Danke für deine Antwort.
Leider verstehe ich es aber noch nie so ganz.. Also vorallem die add Methode.
Also von der Wurzel aus schauen wir, ob wir links einen Nachfolger haben. Ist das der Fall, rufen wir rekursik erneut die Methode auf, so lange, bis wir keinen linken Nachfolger mehr haben. (Wir sind bei einem Blatt angelangt.)
Dieses Blatt müssten wir ja jetzt in unserem Array speichern. Aber was passiert genau bei der add Methode? Wieso müssen wir da noch etwas vergleichen?
Wenn wir ganz links angekommen sind, dann können wir es doch einfach hinzufügen?
Und wieso machen wir dort einen new BinarySearchTree?
Ach herje...Entschuldige bitte meine Unfähigkeit..:/
|
|
| Thema: Binärer Suchbaum in ArrayList einsortieren |
|
|
Und ich habe nochmals eine Frage:
Wenn ich den linken Ast hinzufüge, dann den Knoten und dann den rechten Teilbaum, ist er dann sortiert?
Weil muss ich die Elemente nicht nach "key" sortieren? Und wäre der key nicht bei der Wurzel 0 und würde sich dann so fortsetzen:
0
/ \
1 2
/ \ / \
3 4 5 6
Oder verstehe ich nun alles komplett falsch?!
|
|
| Thema: Binärer Suchbaum in ArrayList einsortieren |
|
|
Meine Frage:
Hallo Zusammen!
Leider stecke ich bei einer Aufgabe fest und weiss einfach nicht, wie ich sie angehen soll.
Und zwar geht es um Folgendes:
Ich soll eine Methode schreiben, die eine (nach dem Schlüssel key) sortierte Liste aller im Binären Suchbaum vorhandenen Elemente (things vom Typ T) zurückgibt.
Das Gerüst sieht folgendermassen aus:
public ArrayList<T>createSortedList ( BinarySearchTree<T> tree) {
return createSortedList(tree, new ArrayList<T>());
}
public ArrayList<T> createSortedList ( BinarySearchTree<T> tree, ArrayList<T> list){
}
Meine Ideen:
Wenn steht, dass sie nach dem Schlüsselwert key sortiert sein soll, dann heisst das, das es keine Rolle spielt, was für ein Wert das jeweilige thing hat. Sondern sortieren nach key heisst, dass ich zuerst die Wurzel ausgib (=0) und dann das 1, 2, 3,.. Element, oder?
Ich habe Mühe, das ganze in eine schöne Liste zu packen.
Kann mir jemand helfen?
|
|
| Thema: Referenzen |
|
|
ok, ich danke dir für deine hilfe!
|
|
| Thema: Referenzen |
|
|
Hallo, ich habe eine Frage bezüglich einer Aufgabe und ich weiss nicht, ob ich sie richtig verstanden habe.
Also ich habe folgende zwei Funktionen:
void proc1 (int* n, int &m)
{
*n = *n +5;
std::cout << *n * m;
}
void proc2 (int* n; int m)
{
*n= *n+5;
std::cout << *n * m;
}
Dazu noch zwei Main Methoden:
Die erste lautet:
int main()
{
int k=5;
proc1(&k,k)
return 0;
}
und die andere lautet:
int main()
{
int k=5;
proc2(&k,k)
return 0;
}
Die Frage ist nun, was die jeweiligen main Funktionen ausgeben.
Ich habe ein bisschen ein Problem mit den Referenzen bzw. nicht-Referenzen.
Ich weiss, dass das die erste Main Funktion 100 ausgibt und die zweite nur 50. Das liegt daran, dass m einmal als Referenz genommen wird und einmal nicht.. Aber kann mir das jemand genau erklären? Irgendwie Schritt für Schritt? Also wann wie was genau verändert wird?
Ich habe manchmal Mühe, mir das aufzuschreiben oder aufzuzeichnen. Also allgemein das Vorgehen bei solchen Aufgaben mit Referenzen.
Ich danke euch vielmals!
|
|
|
| Zeige Beiträge 1 bis 14 von 14 Treffern |
|
|
|
