Klausur vom 23.02.2012 Aufgabe 4

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

Klausur vom 23.02.2012 Aufgabe 4
Ich habe zwar die Lösung im Klausurvorbereitungkurs verfolgt, dennoch habe ich ein paar Verständnisfragen zur Teilaufgabe c) ( a) und b) sind soweit nachvollzogen und verstanden worden)

Ich habe mir folgende Lösung notiert:

Knoten kopf = entferneMax();
Knoten schlepp = kopf;

while(wurzel != null) {

   Knoten max = entferneMax();
   schlepp.rechts = max;
   schlepp = max;  // hier meine Frage

}

return kopf;

→ Sind meine Notizen überhaupt korrekt?, kann sein, dass ich mich verschrieben hab und meine Verwirrung nur daraus resultiert.

Ich verstehe nun nicht ganz wie obiger Code sicherstellt, dass wir einen absteigend, zu einer Liste degnerierten Baum erhalten.
Mit “entferneMax()” wird ja das Maximum des aktuellen Heaps entfernt und anschließen (auf nicht näher erlauterte weiße) die MaxHeap-Eigenschaft hergestellt.
Dabei wird der Knoten aus dem Heap entfernt und all seine Verbindungen auf null gesetzt.

→ hab ich das soweit überhaupt richtig verstanden?

Wenn ich aber nun wiederholt in der Schleife das Maximum entferne und im Knoten max speichere und diesen dann an schlepp.rechts anhänge und anschließend schlepp = max setze, so erhalte ich doch lauter einzelne Knoten mit jeweils nur einem rechten Nachfolger und keinen Baum.

Ich denke mir das ungefähr so, dass wenn ich schlepp = max setze , schlepp anschließend der aktuelle durch entferneMax() erzeugte Knoten ohne Verbindungen wird.

Ich weiß nicht wo mein Denkfehler liegt oder aus welchem Grund ich obigen Code nicht nachvollziehen kann und bitte daher um Hilfe!

Klappt oberer Code vlt auch so?:

while(wurzel != null){

   Knoten max = entferneMax();
   schlepp.rechts = max ;
   schlepp = schlepp.rechts;

}

a=b;
c=b;

ist gleichwertig mit

a=b;
c=a;

dabei spielt es keine rolle ob in den variablen pointer drinstehen oder primitive datentypen.

um deine zweite frage mal zu beantworten.

zur ersten frage:

schau dir mal das bild der aufgabe an.
und wie ein zur Liste degenerierter Baum aussieht.

Will mal jemand seine Lösung zu den anderen Teilaufgaben posten? Hier https://fsi.informatik.uni-erlangen.de/dw/pruefungen/bachelor/aud/loesungws11 fehlt die Aufgabe leider noch.

A4)a)

private void versickern(Knoten k) {

     Knoten groesser = null;

     groesser = k.links;

     if(k.rechts != null){
           if(k.links != null && k.links.wert < k.rechts.wert || k.links == null) {
                             groesser = k.rechts;
           }
    }


    if(groesser == null) {
         return;
    }


    if(groesser.wert <k.wert) return;

    vertausche (groesser, k);

     
    versickern(groesser);

}

4)b)

private void erzeugeHalde(Knoten k) {

   if(k.left != null){
       erzeugeHalde(k.left);
   }

   if(k.right !=null){
       erzeugeHalde(k.right);
   }

   versickern (k);

}

in Aufgabe 2c) ist ein kleiner Fehler in der Lösung:

// Gehe alle Nachbarknoten einmal durch
for(Node n : neighbors) {

statt neighbors müsste es heißen current.neighbors.

Funktioniert hat der Code aber bei mir trotzdem nicht in Java, falls es wem hilft, ich habe noch diese alternative Lösung:

import java.util.;
import static java.awt.Color.;

public class derGraph {

public boolean color(Node v) {
    LinkedList<Node> q = new LinkedList<Node>();
    v.color = BLACK;
    q.addLast(v);

    while (q.isEmpty() != true) {
        Node current = q.removeFirst();

        for (Node n : current.neighbors) {

            if (n.color == current.color) {
                return false;

            }

            if (n.color == WHITE) {
                n.color = (current.color == BLACK ? GRAY : BLACK);
                q.addLast(n);
            }

        }
        System.out.println("Bearbeitet:" + current);
    }
    return true;
}

}

Du kannst im Übrigen selbst die Lösungen korrigieren, wenn du einen Fehler findest.