Du verwendest einen veralteten Browser. Es ist möglich, dass diese oder andere Websites nicht korrekt angezeigt werden. Du solltest ein Upgrade durchführen oder ein alternativer Browser verwenden.
Hallo, ich muss in java Bäume implementieren und habe da ein Problem.
Bei dieser Methode hier:
Code:
public int hoehe()
{
if (nknoten.links==null && nknoten.rechts==null)
return 0;
if (nknoten.links==null)
return 1+nknoten.rechts.hoehe();
if (nknoten.rechts==null)
return 1+nknoten.links.hoehe();
return 1+ Math.max(nknoten.links.hoehe(),nknoten.rechts.hoehe());
gibt der Compiler immer aus das er die Methode hoehe nicht finden kann.
Den Knoten habe ich wie folgt implementiert
Code:
public class Knoten<E>
{
Knoten<E> links;
Knoten<E> rechts;
E value;
public Knoten (Knoten<E> links, Knoten<E> rechts, E
value)
{
this.links=links;
this.rechts=rechts;
this.value=value;
}
}
Kann mit jemand vlt. sagen warum der Compiler die Methode hoehe nicht rekursiv aufrufen kann?
Achso ich habe vergessen zu erwähnen das ich hoehe in einem Interface definiert habe, welches ich nun implementiert habe.
Das was ich gepostet habe ist doch die Methode hoehe die sich rekursiv aufrufen soll, oder sehe ich das falsch?
Mein Interface sieht wie folgt aus:
Code:
import java.util.*;
public interface Baum<E>
{
// Anzahl der Knoten :
public int groesse ();
// Hoehe
public int hoehe ();
// Wurzel
public Knoten<E> wurzel ();
// Inhalt des Knoten v :
public E Inhalt (Knoten<E> v);
// Vater des Knoten v .
public Knoten<E> vater (Knoten<E> v ) throws WurzelException;
// Kinder des Knoten v :
public List<Knoten<E>> kinder (Knoten<E> v ) ;
// gib Knoten v ein weiteres Kind mit Inhalt e
public Knoten<E> weiteresKind (Knoten<E> v , E e );
// Preorder-Liste der gespeicherten Elemente
public List<E> preorder ();
}
Ok
Also Ich habe eine Interface Baum , eine Klasse Knoten und eine Klasse Tree welches das Interface Baum implementiert:
Code:
import java.util.List;
public class Tree<E> implements Baum<E>
{
public Knoten nknoten;
public int groesse = 0;
public int hoehe()
{
if (nknoten.links==null && nknoten.rechts==null)
return 0;
if (nknoten.links==null)
return 1+nknoten.rechts.hoehe();
if (nknoten.rechts==null)
return 1+nknoten.links.hoehe();
return 1+ Math.max(nknoten.links.hoehe(),nknoten.rechts.hoehe());
}
public int groesse()
{
if (nknoten.links==null && nknoten.rechts==null)
return 1;
if (nknoten.links==null)
return 1+nknoten.rechts.groesse();
if (nknoten.rechts==null)
return 1+nknoten.links.hoehe();
return 1+ links.hoehe()+rechts.hoehe();
}
public Knoten<E> wurzel ()
{
if (nknoten.links==null && nknoten.rechts==null)
return nknoten;
else
{
}
}
public E Inhalt (Knoten<E> v)
{
}
public Knoten<E> vater (Knoten<E> v )
{
}
public List<Knoten<E>> kinder (Knoten<E> v )
{
}
public Knoten<E> weiteresKind (Knoten<E> v , E e )
{
}
public List<E> preorder ()
{
}
}
Vielleicht mach ich gerade auch irgend nen Dummen fehler, aber ich komm einfach nicht drauf warum er diese Methode nicht finen kann.
Er kann hoehe() nicht finden, da diese Methode ja gar nicht in der Klasse Knoten vorhanden ist. Ist ja auch eigentlich logisch, ein Knoten weiß doch nichts über die Höhe des Baumes.
Überdenke nochmal genau die Methode hoehe(), sie ist meiner Ansicht nach falsch implementiert. Die Höhe ist doch nichts anderes als der längste Pfad, oder?
Stimmt hät ich ja auch eigentlich selber drauf kommen können
Eigentlich müsste aber diese Methode funktionieren, ich werds mal testen und dann werde ich ja sehen obs klappt.
Vielen Dank nochmals für die Hilfe.
das ist zwar richtig, allerdings ist die Idee, die seiner hoehe()-Funktion zugrunde liegt eine andere. Denn jeder Knoten in einem Baum ist wiederum Wurzel eines (Teil-)Baums, in dem all die Knoten enthalten sind, die 'unterhalb' des Knotens liegen. Somit kann man die Hoehe eines Baums rekursiv errechnen.
Will man also die Höhe eines Baumes wissen, nimmt man sich den Wurzelknoten her. Da es sich in diesem Fall offensichtlich um einen Binärbaum handelt fragt dieser zuerst seinen linken Knoten, wie die Höhe seines Teilbaums ist und dann den rechten Knoten und addiert zum Schluss sich selbst hinzu. Wenn man das rekursiv macht (so wie in dem Code-Beispiel) erhält man die Höhe des gesamten Baums.
Fazit: die hoehe()-Funktion gehört nicht in die Tree-Klasse sondern in die Knoten-Klasse.