Informatik 12/13 (G9)

Diese Seite ist nicht editierbar. Sie können den Quelltext sehen, jedoch nicht verändern. Kontaktieren Sie den Administrator, wenn Sie glauben, dass hier ein Fehler vorliegt.
====== Lösung zur Aufgabe "Höhe des Baumes" ======

<WRAP center round todo 60%>
**Aufgabe 7:** \\ 
Erstelle eine Methode ''public int hoehe()'', die die Höhe des binären Suchbaums zurückgibt. \\ \\  
</WRAP>


<HTML>
<div class="java-online" style="height: 600px; width: 100%" data-java-online="{'withBottomPanel': true, 'id': 'Binaerbaum'}">

<script type="text/plain" title="Binärbaum.java">
public class Binärbaum {
   private Baumelement wurzel;
    
   public Binärbaum() {
      wurzel = new Abschluss();
   }
    
   public void einfügen(int i) {
      wurzel = wurzel.einfügen(i);
   }
    
   public void traverseInOrder() {
      wurzel.traverseInOrder();
   }

   public int getAnzahl() {
      return wurzel.getAnzahl();
   }

   public boolean istEnthalten(int n) {
      return wurzel.istEnthalten(n);
   }
   
   public int höhe(){
      return wurzel.höhe();
   }
}
</script>

<script type="text/plain" title="Baumelement.java">
public abstract class Baumelement {
   
   public abstract Baumelement einfügen(int i);
    
   public abstract void traverseInOrder();

   public abstract int getAnzahl();

   public abstract boolean istEnthalten(int n);
   
   public abstract int höhe();

}
</script>


<script type="text/plain" title="Knoten.java">
public class Knoten extends Baumelement {
   private int inhalt;
   private Baumelement links;
   private Baumelement rechts;
    
   public Knoten(int i) {
      inhalt = i;
      links = new Abschluss();
      rechts = new Abschluss();
   }
    
   public Baumelement einfügen(int i) {
      if(i > inhalt) {
         rechts = rechts.einfügen(i);
      } else {
         links = links.einfügen(i);
      }
      return this;
   }

   public void traverseInOrder() {
      links.traverseInOrder();
      print(inhalt + ", ");
      rechts.traverseInOrder(); 
   }

	public int getAnzahl() {
		return links.getAnzahl() + 1 + rechts.getAnzahl();
	}

	public boolean istEnthalten(int n) {
		return links.istEnthalten(n) || inhalt == n || rechts.istEnthalten(n);
	}

   public int höhe(){
      int höheLinks = links.höhe();
      int höheRechts = rechts.höhe();
      if(höheLinks > höheRechts){
         return höheLinks + 1;
      } else {
         return höheRechts + 1;
      }
   }

}
</script>

<script type="text/plain" title="Abschluss.java">
public class Abschluss extends Baumelement {

   public Baumelement einfügen(int i) {
      return new Knoten(i);
   }
    

  	public void traverseInOrder() {
    		return;
  	}

	public int getAnzahl() {
		return 0;
	}

	public boolean istEnthalten(int n) {
		return false;
	}

   public int höhe(){
      return 0;
   }

}
</script>

<script type="text/plain" title="Testprogramm.java">
Binärbaum baum = new Binärbaum();

baum.einfügen(51);
baum.einfügen(20);
baum.einfügen(96);
baum.einfügen(2);
baum.einfügen(31);
baum.einfügen(92);
baum.einfügen(98);
baum.einfügen(93);
baum.einfügen(87);
baum.einfügen(63); 

baum.traverseInOrder();
println("Anzahl: " + baum.getAnzahl());
println("Ist 31 enthalten? " + baum.istEnthalten(31));
println("Ist 21 enthalten? " + baum.istEnthalten(21));

println("Höhe: " + baum.höhe(), Color.green);
</script>

</div>

</HTML>