/**
 * Beschreiben Sie hier die Klasse binärbaum.
 * 
 * @author (Ihr Name) 
 * @version (eine Versionsnummer oder ein Datum)
 */
import java.util.ArrayList;
public class Binärbaum
{
 //Attribute 
 public Object wert;
 public Binärbaum links;
 public Binärbaum rechts;
  
 //Konstruktoren
 //Konstruktoren für ein Blatt
 
 //Konstruktor für inneren Knoten
 Node Final;
 public void einfügen(int [] Anzahl){
     //alle Nodes werden abgespeichert
     
   ArrayList<Node> m = new ArrayList<Node>();
   
  for(int i =0 ; i<Anzahl.length; i++){
    if(Anzahl[i] >= 1){
        //Node wird angelegt
    Node n = new Node((char)(i + 65), Anzahl[i]) ;
    
    m.add(n);
    }
    } 
    //Sortieren von den Werten 
   
   while(m.size() > 1){
    //Minimum finden
    int Minimum = Minimum(m);
    //ermittelt das Minimum für die Festlegung des rechten Knotens
    Node n1 = m.get(Minimum);
    //entfernt das aktuelle Minimum
    m.remove(Minimum);
    
    int Minimum2 = Minimum(m);
    //ermittelt das Minimum für die Festlegung des linken Knotens
    Node n2 = m.get(Minimum2);
    //entfernt das aktuelle Minimum
    m.remove(Minimum2);
    Node neu = new Node(' ', n1.Anzahl + n2.Anzahl);
    neu.links = n1;
    neu.rechts= n2;
    m.add(neu);    
        }
    Final = m.get(0);
    }
public void ausgeben(Node n, String i){
if(n.links != null){
//gibt Weertee aus und erstellt dabei Binärcode
ausgeben(n.links, i + "0");
ausgeben(n.rechts, i + "1");
}else{
    System.out.println(n.wert + " : " + i+ " Anzahl:" + n.Anzahl);
    n.Binärcode = i;
}

}
public void codieren(String text){
for(int i = 0; i<text.length(); i++){
char Buchstabe = text.charAt(i);
Node n = Suche(Buchstabe, Final);
System.out.print(n.Binärcode);
}
}
public Node Suche(char ü, Node u){
//sucht Node mit gesuchtem Buchstaben im Binärbaum
if(u.wert == ü){
return u;
}
else{
//sucht im linken Teil des Baums
if(u.links != null ){
if(Suche(ü, u.links)!= null){
return Suche(ü, u.links);
}
}
//sucht im rechten Teil des Baumes
if(u.rechts != null){
if(Suche(ü, u.rechts) != null){
return Suche(ü, u.rechts);
}
}
}
return null;
}
public void zurückcodieren(String b){
    String Suche = "";
    for(int i = 0; i<b.length(); i++){
    //sucht Binärcode
    Suche += b.charAt(i);
    Node n = SucheBinärcode(Suche, Final);
    if(n != null){
    System.out.print(n.wert);
    Suche = "";
    }
    }   
}
public Node SucheBinärcode(String ü, Node u){
//sucht Node mit gesuchtem Binärcode im Binärbaum
if(ü.equals(u.Binärcode)){
return u;
}
else{
//sucht im linken Teil des Baums
if(u.links != null ){
if(SucheBinärcode(ü, u.links)!= null){
return SucheBinärcode(ü, u.links);
}
}
//sucht im rechten Teil des Baumes
if(u.rechts != null){
if(SucheBinärcode(ü, u.rechts) != null){
return SucheBinärcode(ü, u.rechts);
}
}
}
return null;
}
public int Minimum(ArrayList<Node> l){
//setzt temporäres Minimum auf der ersten Stelle der ArrayList
int minindex = 0;
for(int i = 0; i<l.size(); i++){
    //Vergleich Anfangsminimum und aktuellem Arraywert
if(l.get(minindex).Anzahl>l.get(i).Anzahl){
  minindex = i;  
}
}
return minindex;
}

}