# eine Knoten aus einem Baum löschen. [SOLVED]



## gambi (24. Mai 2005)

Guten Tag hiermit mache ich meine Einstand hier im Forum 

Ich versuche gerade aus einem Binären Suchbaum ein Element zu entfernen.


```
public Knoten delete( Knoten baum, int key ) throws IllegalArgumentException{
	int schalter=0;
	if(baum == null) throw new IllegalArgumentException("Key ist nicht enthalten");
	else{
		if(key < inhalt) schalter = 1;
		if(key > inhalt) schalter = 2;
		if(key == inhalt) schalter = 3;
		switch (schalter) {
			case 1 :
			links  = delete(baum.links, key);
			return baum;
			case 2 :
			baum.rechts  = delete(baum.rechts, key);
			return baum;
			case 3 :
			if(baum.links == null) return baum.rechts;
			else { 
				if(baum.rechts == null) return baum.links;
				else {  
					Knoten ersatz =  Nachfolger(baum);
					ersatz.links  = baum.links;
					ersatz.rechts = baum.rechts;
					return ersatz;
				}
			}
		}
	}
}
```

Das Problem ist nur das sich der Compiler standhaft mit einem: 
"This method must return a result of type Knoten" weigert, nur wenn ich das einfüge geht ja meine Logik nicht mehr,
oder hab ich da was vergessen und wenn wo?

Danke für die Hilfe
gambi


----------



## bygones (24. Mai 2005)

du hast nur eine return anweisung innerhalb deiner switch / else bedingungen. Der compiler weiß nicht, dass immer ein Fall eintritt. 

D.h. du musst z.b. im ersten else zweig nach dem switch noch ein return einfügen


----------



## gambi (24. Mai 2005)

aber wenn ich das rein schreibe macht er mir doch die ganze rekursion kaputt  
wie kann ich das verhindern?

ps, danke für die schnelle antwort


----------



## Bleiglanz (24. Mai 2005)

javac merkt nicht, dass du immer was zurückgibst

füge einfach als allerletzte Zeile return null; ein oder machs gleich anders

Knoten result = null;

.... ablauflogik

return result;


----------



## Wildcard (24. Mai 2005)

oder so (hab mal die ganzen unnötigen 'else' rausgeschmissen  :wink: ):

```
public Knoten delete(Knoten baum, int key) throws IllegalArgumentException
	{
		int schalter = 0;
		int inhalt = 0;

		if (baum == null)
			throw new IllegalArgumentException("Key ist nicht enthalten");

		if (key < inhalt)
			schalter = 1;
		if (key > inhalt)
			schalter = 2;
		if (key == inhalt)
			schalter = 3;
		switch (schalter)
		{
		case 1:
			links = delete(baum.links, key);
			return baum;
		case 2:
			baum.rechts = delete(baum.rechts, key);
			return baum;
		case 3:
			if (baum.links == null)
				return baum.rechts;
			if (baum.rechts == null)
				return baum.links;

			Knoten ersatz = Nachfolger(baum);
			ersatz.links = baum.links;
			ersatz.rechts = baum.rechts;
			return ersatz;

		default:
			return null;
		}

	}
```


----------



## gambi (24. Mai 2005)

Bleiglanz: 
das problem ist das meine methode rekursiv durch den baum geht und wenn ich
irgendwo ein ergebnis zurückgebe das resutat verfälscht wird. Wenn ich deinen
Vorschlag einfüge nimmt der Compiler den Code zwar an aber ich kann nur den
Kopf löschen bei allen anderen Knoten kommt:
"java.lang.IllegalArgumentException: Key ist nicht enthalten" egal ob der Key enthalten ist oder nicht.

[edit] * thx erstmal ausprobieren ... *
[edit2] 
Danke für die schnelle Hilfe Wildcard aber der bringt trotzdem noch dem Fehler (obwohl der key natürlich enthalten ist) 
ich such mal weiter...


----------



## Wildcard (24. Mai 2005)

Wenn die Felder links oder rechts null sind fliegt natürlich eine Exception. Das musst du entsprechend prüfen und dann die Rekursion beenden.


----------



## gambi (24. Mai 2005)

Für alle die es interessiert hiermal die Lösung, ist sicherlich nicht die beste Variante aber es geht jetzt. 
Dank an euch alle.


```
public Knoten delete(Knoten baum, int key) { 
		  int schalter = 0; 
		  int inhalt = 0; 
		System.out.print("knoten.delete: " + baum.inhalt + "  " + key + "\n");
		if (baum == null) {
		
			System.out.print("NULL\n");
				return null;
		}
		  if ( baum.inhalt >   key ) 
			 schalter = 1; 
		  if ( baum.inhalt <   key ) 
			 schalter = 2; 
		  if ( baum.inhalt == key ) 
			 schalter = 3; 
		  switch (schalter) { 
		  	case 1: 
			System.out.print("case 1\n");
			 	baum.links = delete( baum.links, key ); 
			 	return baum; 
		  	case 2: 
			System.out.print("case 2\n");
			 	baum.rechts = delete(baum.rechts, key); 
			 	return baum; 
		  	case 3: 
				System.out.print("case 3\n");
		  			if( baum.isBlatt( baum ) == 1 ){
		  				baum = null;
						System.out.print("baum.vater.links = null;");
		  				return baum;
		  			}else if( baum.isBlatt( baum ) == 2 ){
		  				baum = null;
						System.out.print("baum.vater.rechts = null;");
		  				return baum;
		  			} else if( baum.isBlatt( baum ) == 0 ){
						return null;
		  			}
			 	if (baum.links == null) {
			 		System.out.print("return baum.rechts");
					return baum.rechts; 
			 	}
			 	if (baum.rechts == null) 
					return baum.links; 
				
				System.out.print("Schluß!");
			 	Knoten ersatz = Nachfolger(baum); 
			 	ersatz.links = baum.links; 
			 	ersatz.rechts = baum.rechts; 
			 	return ersatz; 

		  	default: 
			 	return null; 
		  } 

	   }
```


----------

