Binärer Suchbaum Stackoverflow Problem

[Shibas]

Hi,

ich hab mir eine klasse gebaut mit der ich mir einen Binären Baum erstellen und durchsuchen kann. Mein Problem dabei ist das ich bei größeren Datenmengen nen Stackoverflow bekomme und ich hab nicht so wirklich eine idee was ich an meinen programm ändern könnte damit trozdem funktioniert

package sort;

import core.Daten;
import core.TreeNode;

public class Baum
{

private TreeNode head = null;
private int i = 1;	
private Daten[] db = null;




public Baum(Daten[] db)
{
System.out.println("Baum wird erstellt...");
this.db=db;
this.head = new TreeNode(db[0]);
compare(db[i], head);
}


public void compare(Daten element, TreeNode node)
{
System.out.println("i: "+i+" DB: "+(db.length-1));
if( i <= db.length-1)
{	
	//Wort ist größer als key
	if(element.getWort().compareTo(node.getKey().getWort()) > 0)	
	{
		//System.out.println(element.getWort()+" > "+node.getKey().getWort());
		//System.out.println("Element nach Rechts");
		if(node.getRight()==null)
		{
			node.setRight(new TreeNode(element));
			//System.out.println("eingetragen");
			i++;
			if( i <= db.length-1)
			compare(db[i], head);
		}	
		else
		{
			compare(element, node.getRight());	
		}	

	}	
	
	//Wort ist kleiner als key
	if(element.getWort().compareTo(node.getKey().getWort()) < 0)	
	{
		//System.out.println(element.getWort()+" < "+node.getKey().getWort());
		//System.out.println("Element nach Links");
		if(node.getLeft()==null)
		{
			node.setLeft(new TreeNode(element));
		i++;
		if( i <= db.length-1)
		compare(db[i], head);
		}	
		else
		{
			compare(element, node.getLeft());	
		}
	
	
	
	}



}
else
{
System.out.println("Baum erstellt");	
}


}	
	
public void searchbaum(Daten search, TreeNode node)
{
			
		if(search.getWort().compareTo(node.getKey().getWort()) == 0)
		{
		System.out.println(">>>>>>>>>>>>>>> "+node.getKey().getWort()+" Gefunden!!!");	
		}	
		
		//Wort ist größer als key
		else if(search.getWort().compareTo(node.getKey().getWort()) > 0)	
		{
			System.out.println(search.getWort()+" > "+node.getKey().getWort());
			System.out.println("Suche Rechts");
			if(node.getRight() !=null)
			searchbaum(search, node.getRight());
			else
			System.out.println("Kein Eintrag für <"+search.getWort()+"> gefunden");	
			

		}	
		
		//Wort ist kleiner als key
		else if(search.getWort().compareTo(node.getKey().getWort()) < 0)	
		{
			System.out.println(search.getWort()+" < "+node.getKey().getWort());
			System.out.println("Suche Links");
			
			if(node.getLeft() !=null)
			searchbaum(search, node.getLeft());	
			else
			System.out.println("Kein Eintrag für <"+search.getWort()+"> gefunden");	
		}	
		if(node.getLeft() == null && node.getRight()== null && search.getWort().compareTo(node.getKey().getWort()) != 0)
		{
		System.out.println("Kein Eintrag gefunden");	
		}
	
	
	
}



public TreeNode getHead() {
	return head;
}


public void setHead(TreeNode head) {
	this.head = head;
}


public int getI() {
	return i;
}


public void setI(int i) {
	this.i = i;
}


public Daten[] getDb() {
	return db;
}


public void setDb(Daten[] db) {
	this.db = db;
}	
	

	
}

package core;

public class TreeNode
{

private Daten key;
private TreeNode left = null;
private TreeNode right = null;

public TreeNode(Daten e)
{
key = e;
}


// Getter Setter
public Daten getKey() {
	return key;
}

public void setKey(Daten key) {
	this.key = key;
}

public TreeNode getLeft() {
	return left;
}

public void setLeft(TreeNode left) {
	this.left = left;
}

public TreeNode getRight() {
	return right;
}

public void setRight(TreeNode right) {
	this.right = right;
}


	
	
}

Die Klasse SetTree darf ich leider nicht benutzen.

Währe cool wenn mir jemand sagen könnte wie ich das teil doch noch zum laufen bekomme.

mfg
Shibas

 

[SlaterB]

in deiner compare-Methode hast du unnötigerweise den Folgeaufruf
> i++, compare(db, head);
usw. sogar noch doppelt für links und rechts,

wenn du 1000 Daten hast und jedes Einfügen etwa 5x compare erfordert, so schachtelst du alles ineinander zu 5000 rekursiven Aufrufen,
Java muss sich jeden merken, am Ende ja dorthin zurückkehren, irgendwann ist der Stack voll,

das ist oft genug leider ein normales Problem, in deinem Fall komplett unnötig,
lasse im Konstruktor Baum eine Schleife über das Daten-Array laufen und rufe jeweils compare() auf,
in dieser Methode musst du dich darum dann nicht mehr kümmern und die maximale rekursive Tiefe dürfte im handlich abzählbaren Bereich liegen statt 1000x so hoch

 

[Shibas]

Danke für den Tip funktioniert jetzt einwandfrei^^

package sort;

import core.Daten;
import core.TreeNode;

public class Baum
{

private TreeNode head = null;


public Baum(Daten[] db)
{
System.out.println("Baum wird erstellt...");
this.head = new TreeNode(db[0]);
for(int i =0; i<=db.length-1; i++)
{	
compare(db[i], head);
}
System.out.println("Baum erstellt");
}


public void compare(Daten element, TreeNode node)
{


	
	//Wort ist größer als key
	if(element.getWort().compareTo(node.getKey().getWort()) > 0)	
	{
		//System.out.println(element.getWort()+" > "+node.getKey().getWort());
		//System.out.println("Element nach Rechts");
		if(node.getRight()==null)
		{
			node.setRight(new TreeNode(element));
			//System.out.println("eingetragen");
			
		}	
		else
		{
			compare(element, node.getRight());	
		}	

	}	
	
	//Wort ist kleiner als key
	if(element.getWort().compareTo(node.getKey().getWort()) < 0)	
	{
		//System.out.println(element.getWort()+" < "+node.getKey().getWort());
		//System.out.println("Element nach Links");
		if(node.getLeft()==null)
		{
			node.setLeft(new TreeNode(element));
			
		}	
		else
		{
			compare(element, node.getLeft());	
		}
	}



}

 

[SlaterB]

sind Zeile 42 und 59 noch zu irgendwas gut? zum Glück ignoriert dein erneuter compare-Aufruf Elemente, die schon drin sind
(keine Aktion bei compareTo() == 0),
ansonsten wäre auch schlecht dass du am Anfang db[0] als Head setzt und dann noch per Schleife einfügst,

Zeile 10 solltest du auch aufräumen, Zeile 31 mit dem else dazu ist auch ohne Funktion, die Ausgabe eh was für den Konstruktor

 

[Shibas]

jo hab ich schon gesehn^^