Rekursion im Baum

[Lazyyy]

Hallo zusammen,
Ich hätte folgende aufgabe:

class TreeNode
{
private int Cont = 0;
private TreeNode Left = null;
private TreeNode Rght = null;
public TreeNode(int _Cont, TreeNode _Left, TreeNode _Rght) {
Cont = _Cont;
Left = _Left;
Rght = _Rght;
}
}

Stellt den Kopf dar ... die Aufgabe ist den Baum nach einem X zu durchsuchen und dessen Anzahl wieder zu geben:
Folgenden Ansatz habe ich:

public int countCont(int X){
int anzahl = 0;
if(left!=null){
if(left.Cont == X) anzhal ++;
left.countCont(X);
}
}
if(right!=null){
if(right.Cont == X) anzhal ++;
right.countCont(X);
}
}
return anzahl;

Ich frage mich ob die doppelte If-Bedingung funktioniert und wenn ja wie er ohne left.Next beispielsweise in den nächsten Knoten geht.

Viele Grüße
Lazy

 

[fhoffmann]

Du solltest die Rückgabewerte der rekursiven Aufrufe auch benutzen!

 

[httpdigest]

Und ich würde auch eher this.Cont == X prüfen und die rekursiven Aufrufe nach Abfrage mit != null gleich machen, statt immer explizit left.Cont == X und right.Cont == X zu prüfen.

 

[Lazyyy]

Und ich würde auch eher this.Cont == X prüfen und die rekursiven Aufrufe nach Abfrage mit != null gleich machen, statt immer explizit left.Cont == X und right.Cont == X zu prüfen.

this.cont betrachtet dann einfach den aktuellen Knoten ?

Du solltest die Rückgabewerte der rekursiven Aufrufe auch benutzen!

Ah ..:

public int countCont(int X){
int anzahl = 0;
if(left!=null){
if(this.Cont == X) anzhal ++;
}
}
if(right!=null){
if(this.Cont == X) anzhal ++;
}
}
return anzahl +left.countCont(X)+right.countCont(X);

 

[httpdigest]

Und ich würde auch eher this.Cont == X prüfen und die rekursiven Aufrufe nach Abfrage mit != null gleich machen, statt immer explizit left.Cont == X und right.Cont == X zu prüfen.

public int countCont(int X){
int anzahl = 0;
if(left!=null){
if(this.Cont == X) anzhal ++;
}
}
if(right!=null){
if(this.Cont == X) anzhal ++;
}
}
return anzahl +left.countCont(X)+right.countCont(X);

Du solltest jetzt nicht einfach verbatim jedes left.Cont und right.Cont durch this.Cont ersetzen.... ein bisschen nachdenken darfst du dann schon auch noch.

 

[Lazyyy]

Du solltest jetzt nicht einfach verbatim jedes left.Cont und right.Cont durch this.Cont ersetzen.... ein bisschen nachdenken darfst du dann schon auch noch.

komme leider nicht drauf.

 

[httpdigest]

Schau mal her. Also, was muss ein einzelnes TreeNode in seiner countCont() Methode machen?
1. Es muss schauen, ob es selber ein X hält (also Cont == X). Falls ja: +1
2. Es muss schauen, ob sein linker Kindknoten existiert (left != null) und muss das Ergebnis von dessen countCont() Aufruf aufsummieren
3. Dasselbe (wie bie 2.) muss mit dem rechten Kindknoten gemacht werden
4. Am Ende gibt die aktuelle countCont() Methode das Ergebnis zurück

"I can explain it to you, but I cannot understand it for you."

 

[Lazyyy]

Mich verwirrt unter anderem, dass es kein left.Next oder ähnliches gibt.
Hier wäre mein neuer Ansatz:

public int countCont(int X){
int anzahl = 1;                                                        
if(left!=null){
this.Cont != x ? 0 : anzahl + left.countCont(x);
}
if(right!=null){
this.Cont != x ? 0 : anzahl + right.countCont(x);
}

return anzahl;

 

[httpdigest]

Mich verwirrt unter anderem, dass es kein left.Next oder ähnliches gibt.

Was soll denn ein left.Next dann sein/machen?

public int countCont(int X){
int anzahl = 1;                                                      
if(left!=null){
this.Cont != x ? 0 : anzahl + left.countCont(x);
}
if(right!=null){
this.Cont != x ? 0 : anzahl + right.countCont(x);
}
return anzahl;

Nein, falsch. Nochmal.

Was sollen denn die beiden in der Luft stehenden Ausdrücke this.Cont != x ? 0 : anzahl + left.countCont(x); und this.Cont != x ? 0 : anzahl + right.countCont(x);, die auch nicht compilieren?
Nimm dir doch bitte erstmal eine Java IDE oder ein JDK zur Hand und probiere wenigstens aus, ob deine möglichen Lösungen wenigstens valider Java Code sind.

 

[Lazyyy]

Nochmal

Also:

 public int counCont(int x){
       int anzahl = 0;                          
       if(this.content == x) anzahl++;                              // wenn der Knoteninhalt x entspricht += 1
       if(left!= null){                                                         //linker Kindknoten ..
           anzahl += left.counCont(x);                               //addiere auf anzahl das ergbnis von left.countCont
       }
       if(right!= null){                                                       //rechts analog 
           anzahl += right.counCont(x);
       }
       return anzahl;
    }