Datentypen BinTree Abituraufgabe 2009 ||List

[kit fisto]

Hallo Leute,
ich habe folgendes Verständnisproblem:
Wenn ich einen BinTree habe und den Kopiere um damit zu arbeiten und in dieser Kopie jetzt durch den Baum "wandere" und an einem Blatt ankomme und dort ein neues Object einfüge, dann steht das auch im Originalbaum drin - warum??? Ich arbeite doch nur mit der Kopie?! Wo ist der Zusammenhang. Wohl gemerkt: das Programm läuft iterativ. Bei der Rekursion ist's klar wieso warum weshalb, aber bei der iterativen Programmierung versteh ich nciht ganz warum das funktioniert.
Selbes Phänomen findet man bei der ADT List. Habe ich eine Originalliste mit x Elementen und kopiere diese Liste und füge ein weiteres Object in die Kopie, so ist auch das Original erweitert... Warum???

Vielen Dank im Vorraus,
kitfisto!

 

[Bartleby]

Wie kopierst du denn die Objekte? Etwa so

   Tree tree1 = new BinTree();
   Tree tree2 = tree1;

??

 

[eRaaaa]

Woher sollen wir denn wissen wie du in deinem Code den Baum kopierst? Machst du das so in etwa wie der Vorredner, ist das keine wirkliche Kopie, weil beide Variablen referenzieren den selben Baum..
Die Frage ist ja dann auch ob du eine tiefe Kopie willst/brauchst oder nicht usw...?

 

[faetzminator]

Wenn du's so machst, wie Bartleby fragt, dann kopierst du nur die Referenz des Objektes im Speicher in eine neue Variable. Um Kopien von Daten anzulegen, gibt es mehrere Möglichkeiten:

• die Daten sind primitiv, also int, boolean, long, ... da wird immer gleich der Wert kopiert
• das Objekt ist immutable, generiert also sowieso immer eine neue Instanz im Speicher (wie z.B. String) und gibt diese zurück
• das Objekt ist [c]Cloneable[/c], die Methode [c]clone()[/c] kann aufgerufen werden
• das Objekt stellt einen Konstruktor zur Verfügung, welcher alle Daten des alten Objekts übernimmt (wie z.B. [c]public ArrayList(Collection)[/c])

 

[kit fisto]

ja ich mache das wie schon beschrieben:

BinTree baum1 = new BinTree();
BinTree baum2 = baum1;

Also ändere ich quasi nur die Referenz und arbeite aber in wirklichkeit mit dem Original?! Macht soetwas dann überhaupt Sinn?

 

[faetzminator]

Nein, macht es nicht

 

[kit fisto]

Das ist sehr bedenktlich denn dieser Schritt ist in der Musterlösung zu der Abituraufgabe auf die ich mich beziehe erforderlich...
In dem Programm habe ich einen originalen Baum und den kopiere ich. Dann habe ich einen String der den Pfad angibt den ich durch den Baum gehen muss um das neue Objekt an der passenden Stelle einzufügen. Also je nach Zeichen heißt es dann:

// lBaum entspricht der Kopie des originalen Baums mit dem gearbeitet wird
lBaum = lBaum.getRightTree();
// bzw
lBaum = lBaum.getLeftTree();

So und am Ende wird dann das neue Objekt in lBaum eingefügt. In lBaum steht dann qausi eine Wurzel mit einem Blatt. Dann wird der Ursprungsbaum ausgegeben und dort steht dann auch dieses neue Objekt drin... Könnt ich dann auch einfach mit dem Original arbeiten!?
Es geht mir hier nicht um den Ablauf des Programms sondern wie gesagt nur um den Zusammenhang zwischen Kopie und Original und warum man das so macht wenn da nicht mehr hintersteckt als das man die Referenzen ändert^^

Danke schonmal für die bisherigen Antworten!

 

[faetzminator]

[c]getRightTree()[/c] bzw. [c]getLeftTree()[/c] sagen nichts darüber aus, ob das Original bearbeitet wird oder nicht. Standardmässig gibt eine Gettermethode das Original zurück, meist so:

public BinTree getRightTree() {
    return this.rightTree;
}

Die Implementation könnte aber auch so aussehen:

public BinTree getRightTree() {
    return this.rightTree.clone();
}

 

[kit fisto]

und das sagt mir was!?

Ich meine, wenn ich mir am Ende sowohl das Original als auch die Kopie mittels Inorder() ausgeben lasse, dann
besteht die Kopie wirklich nur aus dieser jeweiligen Wurzel und dem neuen Objekt und das Original ist dann der komplette
Baum mit dem neuen Objekt...

 

[jeppi]

ja ich mache das wie schon beschrieben:
Also ändere ich quasi nur die Referenz und arbeite aber in wirklichkeit mit dem Original?! Macht soetwas dann überhaupt Sinn?

Du meinst generell, nicht wahr?

Das Arbeiten mit Referenzen macht aus objektorientierter Sicht durchaus Sinn, so kannst Du relativ einfach Objekte zum Bearbeiten an eine andere Klassen übergeben. Änderungen, die dann in der "anderen Klasse" am Objekt vorgenommen werden, sind dann auch in der Klasse vorhanden, die das Objekt weitergegeben hat. So als Beispiel. (Und es wird auch noch Speicherplatz dabei gespart, weil Du nicht laufend hin- und zurückkopieren musst.)

Das echte ("tiefe") Kopieren wird deutlich seltener gebraucht, als man zuerst annehmen würde, kann uns Anfängern dann aber spannende Nächte bereiten )

 

[faetzminator]

Die erste Version, der "normale" Getter, lässt dich auf der Originalversion weiterarbeiten. D.h. am Ursprungspunkt macht sich die Änderung auch bemerkbar, da du auf dem gleichen Objekt arbeitest. In der zweiten Version gehe ich davon aus, dass [c]BinTree[/c] [c]Cloneable[/c] und somit die Methode [c]clone()[/c] implementiert. [c]clone()[/c] gibt eine Kopie des Objektes zurück (sollte zumindest, könnte natürlich auch [c]this[/c] zurückgeben). Das heisst aber immer noch nicht, dass es auch eine Deep Copy ist, was in deinem Fall nicht notwenig wär, fallst du für jeden Subnode sowieso wieder [c]clone()[/c] aufrufen würdest.

Was ist nun dein konkretes Problem oder deine Frage?

 

[fastjack]

// lBaum entspricht der Kopie des originalen Baums mit dem gearbeitet wird

Hört sich so an, als ob Du eine Kopie zurückliefern sollst. Steht diese Aufgabe vielleicht im Zusammenhang mit Immutables oder so ?

 

[kit fisto]

Immutables sagt mir jetzt nichts also ich glaube nicht.
Das Programm soll einfach nur neue Objekte gemäß eines vorgegebenen Pfades ordnungsgemäß in den Baum einfügen^^ Und bei der Programmierung ist mir am Ende aufgefallen dass ich mit lBaum ja die ganzen Teilbäume bekomme bis ich nen Blatt habe und dann in lBaum das neue Objekt einfüge und dann war meine Frage - wie kommt jetzt lBaum an den originalen Baum?! So hab ich mir dann mal die Musterlösung angeguckt und die hören da einfach auf und geben das Original aus.
Ich verstehe jetzt einfach nciht wieso das funktioniert!?! Wieso füge ich in lBaum ein und es steht im Original obwohl ich damit eigentlich gar nicht gearbeitet habe und warum nehme ich dann überhaupt sone Kopie?

 

[fastjack]

Whl. ist die Aufgabe seltsam formuliert und meint bestimmt, daß Du immer mit demselben Baum arbeiten sollst. Momentan arbeitest Du ja mit den Referenzen, die nunmal alle auf den Originalbaum zeigen.

 

[Firestorm87]

Ich bin verwirrt und kaufe ein A wie "Aufgabentext"

 

[kit fisto]

sollt ihr haben:

c) Mit einer Zeichenkette kann man die Vorfahrenlinie, also den Weg durch den Baum,
charakterisieren (z. B. Robert bezüglich Justus: Mutter, Mutter, Vater, abgekürzt – ‚mmv’).
(1) Geben Sie die Zeichenkette für Elisabeth bezüglich Justus an.
(2) Entwerfen Sie eine Strategie zur Implementierung einer Methode
public void fuegeHinzu(Ahne pAhne, String pLinie),
die eine neue Person in den Baum einfügt. Dabei soll pLinie die Vorfahrenlinie enthalten.
Der Baum soll in einem Attribut der Ahnenverwaltung mit dem Namen
hatAhnenbaum vorliegen.
Sie können davon ausgehen, dass der Baum mindestens die Wurzel „Justus“ enthält
und pLinie zum Baum passt, d. h., eine Fehlerbehandlung ist nicht erforderlich.
(3) Implementieren Sie die Methode und eventuelle Hilfsmethoden vollständig.
(15 Punkte)

und hier auch nochmal der code der Mustrerlösung:

(3) Iterative Strategie:
public void fuegeHinzu(Ahne pAhne, String pLinie) {
  BinTree lBaum = hatAhnenbaum;
  while (pLinie.length() > 1) {
    if (pLinie.charAt(0) == 'm') {
      lBaum = lBaum.getLeftTree();
   }
   else {
     if (pLinie.charAt(0) == 'v') {
       lBaum = lBaum.getRightTree();
     }
   } // if else
   pLinie = pLinie.substring(1);
  } // while
  BinTree lNeuBlatt = new BinTree(pAhne);
  if ((pLinie.charAt(0) == 'm') {
    lBaum.setLeftTree(lNeuBlatt);
  }
  else {
    if ((pLinie.charAt(0) == 'v') {
      lBaum.setRightTree(lNeuBlatt);
    }
  } // if else
}