Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » aud » Forendiskussionen
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung | |||
pruefungen:bachelor:aud:loesungws11 [18.03.2018 19:33] – Evren | pruefungen:bachelor:aud:loesungws11 [24.01.2019 21:56] (aktuell) – LasagneAlForno | ||
---|---|---|---|
Zeile 146: | Zeile 146: | ||
<code java> | <code java> | ||
- | private void versickern(Knoten k) { | + | private |
- | Knoten groesser = null; | + | Knoten groesser = null; |
- | if(links != null && rechts != null) { | + | if (k.links != null && |
- | groesser = (links.wert > rechts.wert) | + | if (k.links.wert > k.rechts.wert) |
+ | groesser = k.links; | ||
+ | } else { | ||
+ | groesser = k.rechts; | ||
+ | } | ||
- | } else if(links != null) { | + | } else if (k.links != null) { // hier ist es wichtig, ein "else if" statt einem if zu verwenden! |
- | groesser = links; | + | groesser = k.links; |
- | } else if(rechts != null) { | + | } else if (k.rechts != null) { |
- | groesser = rechts; | + | groesser = k.rechts; |
- | } | + | } |
- | if(groesser == null) { | + | if (groesser == null) { |
- | return; | + | return; |
- | } | + | } |
- | if(k.wert > groesser.wert) | + | if (k.wert > groesser.wert) |
- | return; | + | return; |
+ | } | ||
- | vertausche(k, | + | vertausche(k, |
- | versickern(groesser); | + | versickern(groesser); |
- | } | + | |
+ | } | ||
</ | </ | ||
**b)** | **b)** | ||
Nach dem Postorder-Prinzip: | Nach dem Postorder-Prinzip: | ||
<code java> | <code java> | ||
- | private void erzeugeHalde(Knoten k) { | + | private |
- | if(k.left != null) | + | if (k.links != null) |
- | erzeugeHalde(k.left); | + | erzeugeHalde(k.links); |
- | if(k.right != null) | + | if (k.rechts |
- | erzeugeHalde(k.right); | + | erzeugeHalde(k.rechts); |
- | versickern(k); | + | versickern(k); |
- | } | + | } |
</ | </ | ||
**c)** | **c)** | ||
<code java> | <code java> | ||
- | public Knoten inListeSortieren() { | + | public |
- | // Kann leere Halde nicht sortieren | + | // Kann leere Halde nicht sortieren |
- | if (wurzel == null) | + | if (wurzel == null) { |
- | return null; | + | return null; |
+ | } | ||
+ | |||
+ | // Max-Heap-Eigenschaft herstellen | ||
+ | erzeugeHalde(wurzel); | ||
- | // Max-Heap-Eigenschaft herstellen | + | // Wurzel entnehmen und zum Kopf unserer Liste machen |
- | erzeugeHalde(wurzel); | + | Knoten kopf = entferneMax(); |
+ | Knoten schlepp = kopf; | ||
- | // Wurzel entnehmen und zum Kopf unserer Liste machen | + | // Wiederholt Wurzel entnehmen und an Liste anhängen |
- | Knoten kopf = entferneMax(); | + | while (wurzel != null) { |
- | Knoten schlepp = kopf; | + | schlepp.rechts = entferneMax(); |
- | + | schlepp = schlepp.rechts; | |
- | // Wiederholt Wurzel entnehmen und an Liste anhängen | + | } |
- | while(wurzel != null) { | + | |
- | schlepp.rechts = entferneMax(); | + | // Kopf unserer Liste zurückgeben |
- | schlepp = schlepp.rechts; | + | return kopf; |
} | } | ||
- | |||
- | // Kopf unserer Liste zurückgeben | ||
- | return kopf; | ||
- | } | ||
</ | </ | ||