# Binärbaum auf Vollständigkeit prüfen



## Bernd1983 (7. Apr 2006)

hallo, ich möchte einen Binärbaum auf Vollständigkeit prüfen.

Brainstorming:

Baum ist vollständig, wenn alle Blätter selbe Höhe aufweisen.

also eigentlich wenn die Höhe von links und rechts gleich ist.

Rückgabewert soll bool sein. 


bei der Implementierung bekomm ichs nicht ganz gebacken

Bitte um Ratschläge


----------



## SnooP (7. Apr 2006)

Also die Methode soll sein: boolean isVollständig()?
Kannst du da nicht über die Anzahl der Knoten % 2 != 0 gehen? .. war nur grad son Gedanke...
Ansonsten müsstest du den Baum durchwandern bis zu den Blättern und die höhe halt ermitteln


----------



## Ilja (7. Apr 2006)

ganz einfach:

ich gehe davon aus, dass der baum mit verketteten listen implementiert ist?

wenn ja, dann schreibe eine rekursive funktion, die von jedem knoten ausgehend seine beiden unterknoten nacheinander besucht und deren höhe sein, falls der teilbaum volständig ist! anderenfalls false und abbrechen!

die blätter, da die ja keine unterknoten haben, geben 1 zurück und die aufrufende rekursion addiert falls recht-links beides = 1 ist 1 dazu und gibt somit 2 zurück...
die vorangehende rekursion muß also die zurückgegebene höhe der beiden unterzweige vergleichen und dann 1 dazu addieren.... usw.


----------



## Bernd1983 (7. Apr 2006)

also ich habs ja so gemacht:

einfach mal die Höhe ermittelt:


```
int Baumtiefe(){
	  	
	  	return Baumtiefe(root);
	  }

	 int Baumtiefe(Node p){
	 	int links,rechts;
	 	if(p==null){
	 	return 0;
	 	}else{
	 		links=Baumtiefe(p.left);
	 		rechts=Baumtiefe(p.right);
	 	
	 	if(links>rechts){
	 		return links+1;}
	 	else{return rechts+1;}
	 }
```


ja aber wie prüfe ich da mit boolean, ob rechts und links gleich sind?


----------



## Ilja (7. Apr 2006)

in welcher form liegt der baum vor? wie bekommst du den?
was ist über den baum bekannt? anzahl der knoten, blätter?


----------



## Bernd1983 (7. Apr 2006)

so:

class Node{

	Node left;
	Node right;
	int val;
	Node(int val){
		this.val=val;
	}

}//class Node

class Tree{

	Node root;

methoden.......


----------



## Ilja (7. Apr 2006)

```
boolean istVollständig(Node root) {
  // falls beide teilzweige gleich-tief sind und insich vollständig (>=0)
  if(Baumtiefe(root.left) != -1 && Baumtiefe(root.right) == Baumtiefe(root.left))
    return true;
  else
    return false;
}

int Baumtiefe(Node knoten) {
  int links,rechts;
  // wenn Blatt, dann tiefe 0
  if(knoten.val == NULL) return 0;
  links = Baumtiefe(knoten.left);
  if(links >= 0) {
    rechts = Baumtiefe(knoten.right);
    if(rechts != -1 && links == rechts)
      // links-rechts gleich-tief -> return tiefe+1
      return links+1;
    else
      // links-rechts ist unterschiedlich tief!
      return -1;
  } else return -1;
}
```


----------



## Leroy42 (7. Apr 2006)

:shock: Warum nicht einfach

```
boolean istVollständig() {
  return links==null ? rechts==null : rechts != null && links.istVollständig() && rechts.istVollständig()
}
```


----------



## Bernd1983 (7. Apr 2006)

he danke funktioniert klasse


ich wäre selber nie drauf gekommen.

@ilja,leroy bzw alle: gibt es eine Art "algo" wie man solche rekursiven Schritt für Schritt lößt. ich weiß ja wie die rekursion abläuft nur fehlt es mir schwer Algos dafür zu schreiben.

lg

bernd


----------



## Andre_ (8. Apr 2006)

also Leroy42's Lösung ist FALSCH da sie auch vollständig liefert wenn rechts ein vollständiger Baum hängt und links ein Blatt .. dann ist er aber nicht vollständig...
Was er testet ist ob ein Binärbaum *voll*, d.h. jeder innere Knoten hat zwei Kindknoten.

Ilja hat genau diesen Test nicht drin  sein Algorithmus funktioniert wenn der Baum voll ist....


Ich habe jetzt mal beide gemixt und den code ein wenig gestraft!!
Das Rekursionsende ist jetzt wenn kein Knoten übgergeben wird, d.h. bei einem Blatt bei beiden und wenn ein innerknoten eventuell nur ein Kind hat.



```
private static final int NICHT_VOLLSTAENDIG = -1;

boolean istVollständig(Node root) {
    return (Baumtiefe(root) != NICHT_VOLLSTAENDIG);
}

int Baumtiefe(Node knoten) {
  int links,rechts;
 
 // kein Knoten ... tiefe 0
  if(knoten == NULL) 
     return 0;

  links = Baumtiefe(knoten.left);
  if(links != NICHT_VOLLSTAENDIG) {
    rechts = Baumtiefe(knoten.right);
    if(links == rechts) 
      return links+1; // links-rechts gleich-tief -> return tiefe+1
  }
      
  return NICHT_VOLLSTAENDIG;

}
```


----------



## Leroy42 (8. Apr 2006)

Andre_ hat gesagt.:
			
		

> also Leroy42's Lösung ist FALSCH da sie auch vollständig liefert wenn rechts ein vollständiger Baum hängt und links ein Blatt .. dann ist er aber nicht vollständig...
> Was er testet ist ob ein Binärbaum *voll*, d.h. jeder innere Knoten hat zwei Kindknoten.



 :shock: Stimmt!  :shock: 

Da fällt mir die süffisante Bemerkung meines ehemaligen Profs ein:



			
				ExProf hat gesagt.:
			
		

> Ihre (Problem-)Lösung ist wirklich sehr effizient!
> Nur leider nicht effektiv...


----------



## Andre_ (8. Apr 2006)

Algorithmus entwerfen:



			
				Bernd1983 hat gesagt.:
			
		

> Brainstorming:
> 
> Baum ist vollständig, wenn alle Blätter selbe Höhe aufweisen.
> 
> _also eigentlich wenn die Höhe von links und rechts gleich ist._



Soweit schon richtig nur fehlt noch die Bedingung:

_und die beiden Teilbäume auch vollständig sind._




```
int Baumhöhe(Knoten knoten)
{

   if (knoten == null) return 0; // Abbruchbedingung

   int links = baumhöhe(knoten.links);
   int rechts = baumhöhe(knoten.rechts);

  return Math.max(links,rechts)+1;
}

boolean istVollständig(Knoten wurzel)
{
   if ( wurzel == null) return true; //wenn kein knoten dann ist der Vollständig :)

   boolean antwort;
   antwort = (Baumhöhe(wurzel.links) == Baumhöhe(wurzel.rechts));
   antwort = antwort && istVollständig(wurzel.links);
   antwort = antwort && istVollständig(wurzel.rechts);
   return antwort;
}
```

Dieser Code würde jetzt genau das selbe liefern wie der im Beiträg obendrüber ist nur nicht so effizent, ist aber die genaue Umsetzung des Brainstorming! (Baumtiefe berechnet auch wirklich die Baumtiefe  )

Da man jetzt aber die Tiefe der Teilbäume ziemlich häufig doppelt berechnet könnte man sich jetzt überlegen ob man das verbessern könnte!! Allerdings ist der Code oben sehr intuitiv und leicht wartbar was bei größeren Projekten auch einen wichtigen Stellenwert hat.

Das Problem wenn ich beide Funktionen in eine Packen will ist das ich zwei Sachen zurückgeben muss, einmal die Tiefe und einmal ob der Teilbaum vollständig ist. Dieses Problem haben wir in dem Code oben gelöst, indem wir den Tiefenwert _missbraucht_ haben und ihn um ein Flag für den Status, ob er Vollständig ist, erweitert haben.

Man könnte jetzt genausogut dem Knoten um eine Variable Tiefe bzw. vollständig erweitern.


```
class Knoten {
Knoten links;
Knoten rechts;
Object value;
transient int tiefe;  //transient gibt an das der Wert nicht immer aktuell ist 
}

boolean istVollständig(Knoten wurzel)
{
    if ( wurzel == null) return true; //wenn kein knoten dann ist der Vollständig :)

   //zwingend vor der Tiefeberechnung weil diese sonst noch nicht auf die darunterliegenden Knoten ausgeführt wurde
   boolean antwort = istVollständig(wurzel.links) &&  istVollständig(wurzel.rechts);

   // aus dem wird jetzt der Code unten 
   //if (knoten == null) return 0; // Abbruchbedingung
   //
   //int links = baumhöhe(knoten.links);
   //int rechts = baumhöhe(knoten.rechts);
   //
   //return Math.max(links,rechts)+1;
   if (antwort) {
     wurzel.tiefe = 0;
     if (wurzel.links != null)  wurzel.tiefe = Math.max(wurzel.tiefe,wurzel.links);
     if (wurzel.rechts != null) wurzel.tiefe = Math.max(wurzel.tiefe,wurzel.rechts);
     wurzel.tiefe++;
   }

   return antwort;
}
```

Das ist jetzt nur ein Weg es gibt da sehr viele Möglichkeiten wie man das realisieren will... ein schönes Zitat über objektorientiertes Programmieren dazu

*"There are thousand ways to skin the cat"*

noch ein paar Tipps:
Übringens kapselt die Zeile *boolean antwort = istVollständig(wurzel.links) &&  istVollständig(wurzel.rechts);* eine If-Abfrage ... wenn wurzel.links schon nicht vollständig ist dann wird wurzel.rechts nicht berechnet ..

Wenn man richtig Objektorientiert programmieren will würde man die Funktion istVollständig an den Knoten hängen und nicht ihr einen Knoten übergeben ...

Man sollte eigentlich auch keine Umlaute in Variablennamen stecken .. ich habe es aber jetzt mal der besseren Lesbarkeit trotzdem getan


----------



## Bernd1983 (8. Apr 2006)

@Andre

also ich verstehe nicht warum der code von @ilja falsch sein soll. wenn die inneren Koten nicht vollständig sind liefert er false und wenn die Tiefe aller Blätter nicht gleich ist liefert er false.???

lg

bernd


----------



## Andre_ (8. Apr 2006)

wenn der Knoten ein inner Knoten ist aber nur einen Kindknoten hat dann bekommst du da eine NullpointerException...

Beispiel knoten.left = null, knoten.right=irgendein Knoten;



			
				Ilja hat gesagt.:
			
		

> ```
> int Baumtiefe(Node knoten) {
> int links,rechts;
> // wenn Blatt, dann tiefe 0
> ...


----------



## Bernd1983 (8. Apr 2006)

versteh ich nicht ganz zb  t ist mein Baum

t.insert(10);
t.insert(5);
t.insert(3);
t.insert(2);
t.insert(4); -   links

t.insert(15);
t.insert(13);
t.insert(11);
t.insert(14);
t.insert(17);
t.insert(16);
t.insert(18); - rechts

koten (5) ist ein innerer Knoten und der rechte Nachfolger ist null. bekomme klarerweise false und keine exception


Tut mir leid, aber ich verstehe das nicht wie du das meinst.??


----------



## Andre_ (8. Apr 2006)

hmm musst du mal den ganzen Code hier posten oder mir per pn schicken ... oder lädst es irgendwo hoch und schickst mir den link..

Gruß André


----------

