141 lines
3.1 KiB
Java
141 lines
3.1 KiB
Java
|
|
/**
|
|
* 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;
|
|
}
|
|
|
|
}
|