Wie mache ich hier eine Rekursion rein ?

[Xalo]

Hallo,

ich muss hier einen Rot-Schwarzbaum machen im Fach Algorithmen und Datenstruktur. Kann ich die Methode Print auch Rekursiv machen?

Ich bedanke mich im vorraus und frohes Fest.

Mit freundlichen Grüßen Xalo




public class Test {

private Knoten wurzel;
public Integer findeIndex(Character key) {

Knoten x = wurzel;

while (x != null) {
int vergleich = key.compareTo(x.key);
if (vergleich < 0) x = x.linkesKind;
else if (vergleich > 0) x = x.rechtesKind;
else return x.wert;
}
return null;
}

public static final boolean ROT = true;
public static final boolean SCHWARZ = false;

private class Knoten {
private Character key;
private Integer wert;
private Knoten linkesKind, rechtesKind, eltern;
boolean farbe;


Knoten(Character key, Integer wert, boolean farbe) {
this.key = key;
this.wert = wert;
this.farbe = farbe;

}
}

private Knoten linksRotation(Knoten h) {
Knoten x = h.rechtesKind;
h.rechtesKind = x.linkesKind;
x.linkesKind = h;
x.farbe = h.farbe;
h.farbe = ROT;
return x;
}

private Knoten rechtsRotation(Knoten h) {
Knoten x = h.linkesKind;
h.linkesKind = x.rechtesKind;
x.rechtesKind = h;
x.farbe = h.farbe;
h.farbe = ROT;
return x;
}

public void tauscheFarben(Knoten h) {
h.farbe = ROT;
h.linkesKind.farbe = SCHWARZ;
h.rechtesKind.farbe = SCHWARZ;

}

private boolean istRot(Knoten x) {
if (x == null) return false;
return x.farbe == ROT;

}

public void put(Character key, Integer wert) {
wurzel = put(wurzel, key, wert);

}

public Knoten put(Knoten h, Character key, Integer wert) {
if (h == null) {
return new Knoten(key, wert, ROT);
}
int vergleich = key.compareTo(h.key);

if (vergleich < 0) {
h.linkesKind = put(h.linkesKind, key, wert);
} else if (vergleich > 0) {
h.rechtesKind = put(h.rechtesKind, key, wert);
} else {
h.wert = wert;
}

if (istRot(h.rechtesKind) && !istRot(h.linkesKind)) {
h = linksRotation(h);
}
if (istRot(h.linkesKind) && istRot(h.linkesKind.linkesKind)) {
h = rechtsRotation(h);
}
if (istRot(h.linkesKind) && istRot(h.rechtesKind)) {
tauscheFarben(h);
}
return h;
}
public void print(){
System.out.println(wurzel.key);

System.out.println(wurzel.linkesKind.key);
System.out.println(wurzel.rechtesKind.key);

System.out.println(wurzel.linkesKind.linkesKind.key);
System.out.println(wurzel.linkesKind.rechtesKind.key);

System.out.println(wurzel.rechtesKind.rechtesKind.key);
System.out.println(wurzel.rechtesKind.linkesKind.key);

System.out.println(wurzel.linkesKind.linkesKind.linkesKind.key);
//System.out.println(wurzel.rechtesKind.rechtesKind.rechtesKind.key);

}

public static void main(String[] args) {

char[] a = {'W', 'E', 'I', 'H', 'N', 'A', 'C', 'H', 'T', 'E', 'N'}; //char array erstellt//

Test Baum = new Test();

for (char i = 0; i < a.length; i++) {
Baum.put(a, i + 1);
}
Baum.print();



}

}

 

[MoxxiManagarm]

1. Bitte nutze Java Code-Tags
2. Dein Code kann ein wenig verbessert werden.
z.B.

private boolean istRot(Knoten x) {
  if (x == null) return false;
  return x.farbe;
}

3. zu deiner Frage: Ja das geht und ist auch die sinnvollste Variante hier, aber die gleiche Reihenfolge der Ausgabe wird schwierig.

 

[Xalo]

1.Sorry, bin leider nicht so oft hier deshalb wusste ich das nicht mit denn Tags
2. Wow vielen dank für denn Tipp, gibt's noch mehr stellen wo ich das besser machen kann bzw optimieren kann?
3. Kannst du mir sagen wie das hier geht ich hab's zwar probierte bin aber leider relativ neu was das programmieren angeht und hab mich noch nicht so gut mit Rekursionem beschäftigt bzw. Es fällt mir schwer das nachzuvollziehen

Vielen Dank im übrigen das du dir die Zeit genommen hast und die das angeschaut hast

 

[MoxxiManagarm]

2)
- Wenn du die Wrapper Klassen für int und char nicht zwingend benötigst wäre es besser wenn du den primitiven Datentyp verwendest
- Brauchst du wirklich den eltern Knoten?
- Entsprechend der Namenskonvention sollte deine Instanz der Klasse Test nicht Baum sondern baum heißen
- Wieso nennst du die Klasse nicht Baum anstatt Test?
>> Insgesamt ist dein Code ziemlich gut für einen Anfänger! Meine Anmerkungen sind eher Kleinigkeiten
3) Deine Knoten sind immer Teilbäume. Du hast verschiedene Möglichkeiten den Baum auszugeben: Preorder (selbst, links, rechts), Inorder (links, selbst, rechts), Postorder (links, rechts, selbst)

Hier ein Beispiel für inorder, es verdeutlich es glaube ich besser als alle Worte:

public void print() {
  if(left != null) left.print();
  System.out.println(/*printself*/);
  if(right != null) right.print();
}

 

[Xalo]

Danke dir ,ich habe denn nicht ganz alleine gemacht , meine Professorin gibt uns immer einen teil vor damit es nicht zu schwer wird. Das was du am Ende beschrieben hast war das die Rekursion ?

Danke dir nochmal für deine Hilfe

 

[MoxxiManagarm]

Ja war es.

 

[Xalo]

Kannst du mir sagen woher du die Werte
public void print() {
if(left != null) left.print();
System.out.println(/*printself*/);
if(right != null) right.print();
}
left und right hast also wie würde ich das mit denn Attributen machen die ich bei mir habe ?

 

[MoxxiManagarm]

Das war doch nur ein Beispiel. Bei dir heißen sie nur anders