Binärbaum auf Vollständigkeit prüfen

[Bernd1983]

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]

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]

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]

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]

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

 

[Bernd1983]

so:

class Node{

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

}//class Node

class Tree{

Node root;

methoden.......

 

[Ilja]

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]

:shock: Warum nicht einfach

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

 

[Bernd1983]

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_]

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]

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:

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

 

[Andre_]

Algorithmus entwerfen:

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]

@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_]

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;

int Baumtiefe(Node knoten) {
  int links,rechts;
  // wenn Blatt, dann tiefe 0
  if(knoten.val == NULL) return 0; <---- knoten ist hier null -> null.val -> exception 
  links = Baumtiefe(knoten.left); <---- Hier wirst du dann Baumtiefe(null) aufrufen!! dann kommst du im nächsten durchlauf zu der Zeile obendrüber
  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;
}

 

[Bernd1983]

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_]

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é