# Benutzer:Dirk Huenniger/huffman

Zur Navigation springen Zur Suche springen
```import Data.List
data Tree = Leaf Integer Char | Node Integer Tree Tree

instance Eq Tree
where
(==) n1 n2  = x == y
where
x= fn n1
y= fn n2

instance Ord Tree
where
compare n1 n2
| x == y    =  EQ
| x <= y    =  LT
| otherwise =  GT
where
x= fn n1
y= fn n2

fn n= case n of
Node i n1 n2 -> i
Leaf i c -> i

basetree x = map  (\(c,i)-> Leaf i c) x

takefirst x = (y,delete y x)
where y = minimum x

step [x] = x
step x = step \$ (Node ((fn y) + (fn z)) y z):zs
where
(y,ys)=takefirst x
(z,zs)=takefirst ys

output (Node _ n1 n2) = (f n1 '0')++ (f n2 '1')
where
f n r = (map (\(c,x)->(c,r:x)) (output n))
output (Leaf _ c) = [(c,[])]

huffman = sort .output . step . basetree

main = print \$ huffman [('a',45),('b',13),('c',12),('d',16),('e',9),('f',5)]
```
```import java.util.*;

public class Hello {
public static void main(String[] args) {
Tree[] array = {new Leaf('a',45),new Leaf('b',13),new Leaf('c',12),new Leaf('d',16),
new Leaf('e',9),new Leaf('f',5)};
ArrayList<Tree> list = new ArrayList<Tree>(Arrays.asList(array));
while (list.size()>1){
Collections.sort(list);
Tree x= list.remove(0);
Tree y= list.remove(0);
}
Tree tree = list.get(0);
List<Pair> pairlist = tree.flatten();
Collections.sort(pairlist);
System.out.println(pairlist);
}
}

abstract class Tree implements Comparable<Tree> {
protected int num;
protected Tree(int num){
this.num=num;
}
public int compareTo(Tree o){
return this.num-o.num;
}
public abstract List<Pair> flatten();
}

class Leaf extends Tree {
private char c;
public Leaf(char c, int num){
super(num);
this.c=c;
}
public List<Pair> flatten(){
ArrayList<Pair> list = new ArrayList<Pair>();
return list;
};
}

class Node extends Tree {
private Tree t1,t2;
public Node(Tree t1,Tree t2, int num) {
super(num);
this.t1=t1;
this.t2=t2;
}
static Node sum(Tree t1,Tree t2){
return new Node(t1,t2,t1.num+t2.num);
}
private static List<Pair> flattenhelper(List<Pair> l, String s){
List<Pair> list= new ArrayList<Pair>();
for (Pair p:l) {
}
return list;
}
public List<Pair> flatten(){
List<Pair> list= flattenhelper( t1.flatten(),"0");
return list;
};
}

class Pair implements Comparable<Pair>{
public char c;
public String s;
public Pair(char c,String s) {
this.c=c;
this.s=s;
}
public int compareTo(Pair o){
if (this.c-o.c!=0) {
return this.c-o.c;
} else {
return this.s.compareTo(o.s);
}
}
public String toString(){
return "("+(new Character(c)).toString()+","+s+")";
}
}
```