[JAVA] Wo liegt der Denkfehler? Laufzeitproblem

Y

Yamagatschi

Gast
Hiho,

Thema ist der Aufbau eines Binärbaumes per Java.

Folgendes Problem. Ich muss die rekursive Methoden insert in eine iterative Methode insertloop schreiben. Nun dachte ich am Anfang "ist doch easy" aber irgendwie habe ich einen gewaltigen Denkfehler, und ich finde ihn einfach nicht.

Die Schleife geht, sobald man die 2 einfühgt, nichtmehr in die IF, damit die Schleife abbricht und das elem eingefühgt wird + 2 Objekte left/right, sondern wiederholt andauernd die else und die IF2.

Ich kann einfach nicht nachvollziehen warum, da ich die hand-Referenz ja dauernd "aktualisiere" und dann MUSS doch irgendwann null als item erscheinen, wenn er die Objekte "durchgeht".

Paar Infos, wo mein Fehler liegt, wären sehr nett. Hier liegen schon dutzend vollgeschriebene Blätter, auf denen ich das Problem durchgehe, aber irgendwie erschließt sich mir die Dauerschleife nicht ...

Ich bedanke mich schon Mal im Vorraus für die Hilfe.

MfG

Yama

Code:
class BinTree
{
	private Comparable item;
	private BinTree left, right;
	
	public void insert(Comparable elem)
	{
		if (item == null)
		{
			item = elem;
			left = new BinTree();
			right = new BinTree();
		} 
		else 
		{
			BinTree next;
			
			if (item.compareTo(elem) > 0)
				next = left;
			
			else
				next = right;
			
			next.insert(elem);
		}
	}

	public void insertLoop(Comparable elem)
	{
		boolean check = false;
		BinTree hand = this;
		
		while(check == false)
		{
			System.out.println("While");
			if(hand.item == null)
			{
				System.out.println("IF");
				check = true;
				
				hand.item = elem;
				hand.left = new BinTree();
				hand.right = new BinTree();
			}
			else
			{
				System.out.println("ELSE-");
				if(hand.item.compareTo(elem) > 0)		
				{
					System.out.println("IF2");
					hand = left;
				}
				else									
				{
					System.out.println("ELSE2");
					hand = right;
				}
			}
		}
			
	}
	
	public Comparable search(Comparable elem)
	{
		if (item == null)
			return null;
		int res = item.compareTo(elem);
		if (res == 0)
			return item;
		return ((res > 0) ? left : right).search(elem);
	}

	public String toString()
	{
		if (item == null)
			return "";
		return left.toString() + item.toString() + " " + right.toString();
	}

    public static void main(String[] args)
    {
//        BinTree tree = new BinTree();
//        tree.insert(5);
//        tree.insert(4);
//        tree.insert(2);
//        tree.insert(1);
//        tree.insert(3);
//        tree.insert(10);
//        tree.insert(6);
//        tree.insert(12);
//        tree.insert(8);
//        System.out.println(tree);
    	
    	BinTree tree = new BinTree();
    	tree.insertLoop(5);
    	System.out.println();
    	tree.insertLoop(4);
    	System.out.println();
    	tree.insertLoop(2);
//    	System.out.println();
//    	tree.insertLoop(1);
//    	System.out.println();
//    	tree.insertLoop(3);
//    	System.out.println();
//    	tree.insertLoop(10);
//    	System.out.println();
//    	tree.insertLoop(6);
//    	System.out.println();
//    	tree.insertLoop(12);
//    	System.out.println();
//    	tree.insertLoop(8);
//    	System.out.println();
    	System.out.println(tree);
    }
}
 
Zuletzt bearbeitet von einem Moderator:
Überlege mal ganz genau nach, was für Werte der Variable "hand" zugewiesen werden und woher diese kommen. ;)
Code:
if(hand.item.compareTo(elem) > 0)	
{
System.out.println("IF2");
hand = left;
}
else	
{
System.out.println("ELSE2");
hand = right;
}
 
Hiho,

Boah ey wie blöd. Hab mich glaube ich zu sehr von der Rekursion mitreisen lassen :D
Da stimmt die Logik im Kopf und dann so ein Fauxpas. Jetzt scheints zu gehen.

Vielen Dank!

Dann mal jetzt zur nächsten Aufgabe, Damenproblem.

_____

PS: Falls jmd. mal so dumm denkt wie ich :)

Code:
if(hand.item.compareTo(elem) > 0)		
{
	//System.out.println("IF2");
	hand = hand.left;
}
else									
{
	//System.out.println("ELSE2");
	hand = hand.right;
}

MfG

Yama
 
Zuletzt bearbeitet von einem Moderator:
Zurück
Oben