Introduction
Complete the implementation of the BuildOptimalHuffmanTree class per directions in the file attached with the assignment posted in Google Classroom.
That is, first complete the constructor, getFrequuencyTable() methods
and complete the getOptimalTree() method.
Class HuffmanNode is include and does NOT need to be changed. You are welcome to add additional helper methods as described n the file attached with the assignment posted in Google Classroom.
Alternatively, see comments.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
import java.lang.*;
import java.util.*;
import java.lang.Math;
/**
* @author Don Allen
*/
class BuildOptimalHuffmanTree
{
private Map<String, Integer> letterFrequenceMap;
/*
* No two chars in letters will have the same getFrequency
*
*/
public BuildOptimalHuffmanTree(String letters)
{
letterFrequenceMap = new HashMap<String,Integer>();
for(char c:letters.toCharArray())
{
if(letterFrequenceMap.get(""+c)!=null)
{
letterFrequenceMap.put(""+c,letterFrequenceMap.get(""+c)+1);
}
else
{
letterFrequenceMap.put(""+c,1);
}
}
}
/*
*/
public Map<String, Integer> getFrequencyTable()
{
return letterFrequenceMap;
}
public HuffmanNode getOptimalTree(){
Map<Integer,String> map = new HashMap<Integer,String>();
for(String s:letterFrequenceMap.keySet())
map.put(letterFrequenceMap.get(s),s);
List<HuffmanNode> list = new ArrayList<HuffmanNode>();
while(map.keySet().size()>0)
{
int min = Collections.min(map.keySet());
list.add(new HuffmanNode(map.get(min),null,null,min));
map.remove(min);
}
while(list.size()>1){
HuffmanNode min = list.remove(0);
HuffmanNode mun = list.remove(0);
int f = min.getFrequency() + mun.getFrequency();
HuffmanNode com = new HuffmanNode("",min,mun,f);
if(list.size()==0)
{
return com;
}
int x = 0;
while(list.get(x).getFrequency()<f)
{
x++;
if(x==list.size())
{
break;
}
}
list.add(x,com);
}
return null;
}
}
/**
* Write a description of class HuffmanNode here.
*
* @author (your name)
* @version (a version number or a date)
*/
class HuffmanNode
{
// instance variables
private String str;
private HuffmanNode left;
private HuffmanNode right;
private int freq;
/**
* Constructor for objects of class HuffmanNode
*/
public HuffmanNode(String s, HuffmanNode l, HuffmanNode r, int f)
{
str = s;
left = l;
right = r;
freq = f;
}
public HuffmanNode getLeft()
{
return left;
}
public HuffmanNode getRight()
{
return right;
}
public String getValue()
{
return str;
}
public int getFrequency()
{
return freq;
}
public void setFrequency(int f)
{
freq = f;
}
}