Suchbaum testen probleme Java

[tukan]

Hallo!

Ich habe ein Problem bei einer Aufgabe. Es geht um Suchbäume.

Es ist Baum gegeben und man soll ihn testen (diese Methode soll noch geschrieben werden), ob es ein Suchbaum ist.

public class Knoten
{
//Attribute
private int schluessel;
private Knoten teilbaumLinks;
private Knoten teilbaumRechts;

//Konstruktor
public Knoten(int schluessel, Knoten teilbaumLinks, Knoten teilbaumRechts)
{
this.schluessel = schluessel;
this.teilbaumLinks = teilbaumLinks;
this.teilbaumRechts = teilbaumRechts;
}

//Standardoperationen
public int getSchluessel() 
{ 
return schluessel; 
}

public Knoten getKnotenLinks() 
{ 
return teilbaumLinks; 
}

public Knoten getKnotenRechts() 
{ 
return teilbaumRechts; 
}

public void setSchluessel(int schluessel) 
{
this.schluessel = schluessel; 
}

public void setKnotenLinks(Knoten teilbaumLinks) 
{
this.teilbaumLinks = teilbaumLinks; 
}

public void setKnotenRechts(Knoten teilbaumRechts) 
{
this.teilbaumRechts = teilbaumRechts; 
} 
}

public class Baeume
{
// Erzeugt einen Baum, der als Wurzel einen Knoten mit dem Schlüsselwert 'schluessel'
// besitzt und diesen Knoten mit den übergebenen Teilbäumen über den linken und rechten
// Nachfolger verknüpft.
public static Knoten add(int schluessel, Knoten teilbaumLinks, Knoten teilbaumRechts)
{
return new Knoten(schluessel, teilbaumLinks, teilbaumRechts);
}

// Erzeugt einen Knoten ohne Nachfolger
public static Knoten add(int schluessel)
{
return add(schluessel, null, null);
}

// Gibt ein Knoten-Feld zurück, in dem jedes Element die Wurzel eines Baums ist
public static Knoten[] getBaeume()
{
Knoten[] k = new Knoten[5]; 
k[0] = add(27, add(15,add(1, add(0), null),
add(18, add(17),
add(20, add(19),
add(25, null, add(26))))),
add(30, add(29),
add(40, add(35), add(42)))); 
k[1] = null; 
k[2] = add(42, add(31, add(19),
add(40, add(42), add(31))),
add(50, add(45), add(52))); 
k[3] = add(35, add(17, add(15, add(16), null),
add(20, add(19), add(21))),
add(40, add(39), add(41))); 
k[4] = add(42); 
return k;
}
}

In dieser Klasse soll die Methode geschrieben werden:

public class Suchbaum
{
public static void main(String[] args)
{
// 'baeume' enthält die Wurzelknoten der zu überprüfenden Bäume
Knoten[] baeume = Baeume.getBaeume();

for (int i = 0; i < baeume.length; i++)
{
System.out.print("Baum " + i + ": Suchbaumeigenschaft ist ");
if (checkTree(baeume[i]) == false)
{
System.out.print("nicht ");
}
System.out.println("erfüllt.");
}
}

// Diese Methode soll einen von Ihnen entwickelten Algorithmus ausführen,
// der die Suchbaum-Eigenschaft eines Baums überprüft. Übergeben wird der
// Wurzel-Knoten des Baums. Das Programm darf nicht abstürzen.
public static boolean checkTree(Knoten k)
{
//Wenn Baum leer, dann soll er true zürückgeben
//dieser code wurde von mir eingefügt
if(k.equals(null)
{
return true;
}
//Bitte um hilfe!!!
return false; 
}
}

 

[antid0te]

Schön wär gewesen wenn die Frage nicht irgendwo verborgen im Quellcode steht...
Was genau ist denn dein Problem?
Fehlt dir
a) eine Idee wann Definition eines Suchbaums erfüllt ist?
b) Was die Def. eines Suchbaums ist?
oder
c) Wie man das umsetzt?
a+b lassen sich sicherlich googlen...
bei c) wäre es lieb die Definition die ihr bei Aufgabenstellung benutzt habt auch uns zugänglich zu machen

 

[JavaFornia]

Die Aufgabe ist es, die Methode checkTree in Suchbaum.java so zu ergänzen, dass der übergebene Binärbaum auf seine Suchbaum-Eigenschaft "true bedeutet erfüllt"

Dabei soll darauf geachtet werden das :

Die anderen Module und Methoden dürfen nicht verändert werden.

Der Algorithmus soll rekursiv formuliert werden.

Ein leerer Binärbaum erfüllt immer die Suchbaum-Eigenschaft.

Ich weiß leider nicht wie man das genau machen soll.

 

[antid0te]

Ja, jetzt wäre noch zu klären was einen Suchbaum ausmacht oder?

 

[JavaFornia]

Entschuldige ich hab nicht ganz verstanden was du meintest.

 

[antid0te]

Was sollst du denn tun?
Einen Baum testen ob es ein Suchbaum ist...
Wie tust du das?
In dem tu den Baum testest ob er alle Kriterien erfüllt die ein Suchbaum erfüllen soll..
Welche sind das?

 

[JavaFornia]

Ja ich muss doch von der Wurzel ausgehen und dann prüfen, ob der jeweilige Knoten bzw. sein Schlüssel kleiner oder größer als der gesuchte Knoten ist

 

[tukan]

Ich weiß leider nicht so genau, wie man das umsetzt. und hätte da gerne unterstützung bei.

Hier eine kleine Definition, was ein Suchbaum ist:
Ein Suchbaum ist ein Baum, bei dem die Knoten des linken Teilbaums eines Knotens nur kleinere Werte und die Knoten des rechten Teilbaums eines Knotens nur größere oder gleichgroße Werte als der Knoten selbst besitzen.

Man kann es sich in etwa so vorstellen:

18
17 25
16 24 26

mfg

tukan

 

[stelzi]

Ich habs mal eben ausgecodet, sollte nicht so schwer sein zu durchschauen auch ohne Kommentar. Der Code ist sicher noch optimierbar, aber wenns darum geht kann man sich auch was fertiges googeln. Bäume sind mit die wohl älteste Datenstruktur in der Informatik und bereits ausreichend perfektioniert

public class Suchbaum {
public static void main(String[] args) {
// 'baeume' enthält die Wurzelknoten der zu überprüfenden Bäume
Knoten[] baeume = Baeume.getBaeume();

for (int i = 0; i < baeume.length; i++) {
System.out.print("Baum " + i + ": Suchbaumeigenschaft ist ");
if (checkTree(baeume[i]) == false) {
System.out.print("nicht ");
}
System.out.println("erfüllt.");
}
}

// Diese Methode soll einen von Ihnen entwickelten Algorithmus ausführen,
// der die Suchbaum-Eigenschaft eines Baums überprüft. Übergeben wird der
// Wurzel-Knoten des Baums. Das Programm darf nicht abstürzen.
public static boolean checkTree(Knoten k) {
if (k == null)
return true;
Knoten linkerknoten = k.getKnotenLinks();
Knoten rechterknoten = k.getKnotenRechts();
if (linkerknoten != null) {
if (linkerknoten.getSchluessel() < k.getSchluessel()) {
checkTree(linkerknoten);
} else
return false;
}
if (rechterknoten != null) {
if (rechterknoten.getSchluessel() > k.getSchluessel()) {
checkTree(rechterknoten);
} else
return false;
}
return true;
}

}

Bitte ausgiebig testen vorher.
*edit*
hab selber noch grade eine Spezialfall gefunden bei dem mein Algorithmus fälschlicherweise true zurück gibt. Also perfekt ist der noch nicht ^^
Wenn ich morgen noch Bock und Zeit habe werd ich daran arbeiten.
Bzw das kannst natürlich auch selbst

 

[tukan]

Danke das hilft mir auf jeden fall schon viel weiter. Vielen Dank

mfg tukan

 

[stelzi]

So also, ich hab jetzt nochmal ne funktionierende Lösung ausgecodet.
Hab aber das Gefühl das es nicht ganz das ist was ihr fabrizieren sollt

Vielleicht schaffst du ja noch eine bessere Lösung bzw. kannst das Zwischenspeichern der Knoten in eine Liste überflüssig machen

import java.util.LinkedList;

public class Suchbaum {
public static void main(String[] args) {
// 'baeume' enthält die Wurzelknoten der zu überprüfenden Bäume
Knoten[] baeume = Baeume.getBaeume();

for (int i = 0; i < baeume.length; i++) {
System.out.print("Baum " + i + ": Suchbaumeigenschaft ist ");
if (checkTree(baeume[i]) == false) {
System.out.print("nicht ");
}
System.out.println("erfüllt.");
}
}

// Diese Methode soll einen von Ihnen entwickelten Algorithmus ausführen,
// der die Suchbaum-Eigenschaft eines Baums überprüft. Übergeben wird der
// Wurzel-Knoten des Baums. Das Programm darf nicht abstürzen.

public static boolean checkTree(Knoten k) {
// Liste zum Speichern der Knotenpunkte
LinkedList knotenliste = new LinkedList();
// Liste füllen
getNodes(k, knotenliste);
// jetzt wird die Liste der Reihe nach durchgegangen und mit dem nächsten
// Element verglichen. Ist das vorhergehende größer als das folgende muss
// ein Fehler vorliegen und daher ist eine Suchbaumeigenschaft nicht mehr
// gegeben.
Knoten tmpk = null;
for (Knoten knoten : knotenliste) { 
// Nötig da beim ersten Durchlauf tmp = null ist
if(tmpk != null)
if(tmpk.getSchluessel() > knoten.getSchluessel())
return false;
tmpk = knoten; 
}
return true;
}

// Diese Methode speichert alle Knoten des Baumes in eine Liste und zwar
// durch in-order Traversierung, d.h zuerst der linke Unterbaum, dann die Wurzel,
// dann der rechte Unterbaum
public static void getNodes(Knoten k, LinkedList knotenliste) {
if (k != null) {
if (k.getKnotenLinks() != null) {
getNodes(k.getKnotenLinks(), knotenliste);
} 
knotenliste.add(k); 
if (k.getKnotenRechts() != null) {
getNodes(k.getKnotenRechts(), knotenliste);
} 
}
}

}