I am now making the huffman algorithm. I have generated the tree but I cannot generate the codes.. please if anyone can help tell me how?
This is the class Node
public class Node
{
private Node left=null;
private Node right = null;
private Node parent = null;
boolean visited = false;
int weight;
String data;
String code;
public Node() {
}
public void setLeft(Node l)
{
left = l;
}
public void setRight(Node r)
{
right = r;
}
public void setParent(Node p)
{
parent = p;
}
public void setWeight(int w)
{
weight = w;
}
public void setData(String d)
{
data = d;
}
public void setCode(String c)
{
code = c;
}
////////////////////////
public Node getLeft()
{
return left;
}
public Node getRight()
{
return right;
}
public Node getParent()
{
return parent;
}
public int getWeight()
{
return weight;
}
public String getData()
{
return data;
}
public String getCode()
{
return code;
}
public String toString()
{
return getData()+" "+getWeight()+" ";
}
}
This is the Compressor Code
import java.io.IOException;
import java.io.RandomAccessFile;
import java.util.ArrayList;
import java.util.Stack;
public class Compressor
{
Compressor(RandomAccessFile source,RandomAccessFile destination) throws IOException
{
RandomAccessFile file = source;
StringBuffer input=new StringBuffer();
ArrayList<String> ch = new ArrayList<String>();
ArrayList<Integer> ints = new ArrayList<Integer>();
ArrayList<Node> tree = new ArrayList<Node>();
//Reading From File
while(file.getFilePointer()<file.length())
{
input.append(file.readLine());
if(file.getFilePointer()!=file.length())
{
input.append("\n");
}
}
System.out.println(input);
//ArrayList of freq and chars
for(int l=0;l<input.length();l++)
{
String x="";
x+= input.charAt(l);
if(ch.lastIndexOf(x)==-1)
{
ch.add(x);
ints.add(1);
}
else
{
ints.set(ch.lastIndexOf(x), ints.get(ch.lastIndexOf(x))+1);
//ints.set(ch.lastIndexOf(input.charAt(l)), ints.get(ch.lastIndexOf(input.charAt(l)))+1);
}
}
//Arraylist Of Nodes
for (int i=0;i<ch.size();i++)
{
Node n1 = new Node();
n1.setData(ch.get(i));
n1.setWeight(ints.get(i));
tree.add(n1);
}
//Sorting the Nodes
simSort(tree);
for (int i=0;i<tree.size();i++)
System.out.println(tree.get(i).getData()+" "+tree.get(i).getWeight());
System.out.println(tree.toString().toString());
//Building the tree
while(tree.size()!=1)
{
Node parent = new Node();
parent.setWeight(tree.get(tree.size()-1).getWeight()+tree.get(tree.size()-2).getWeight());
parent.setRight(tree.get(tree.size()-1));
parent.setLeft(tree.get(tree.size()-2));
parent.setData(tree.get(tree.size()-2).getData()+tree.get(tree.size()-1).getData());
tree.remove(tree.size()-1);
tree.remove(tree.size()-1);
tree.add(parent);
tree.trimToSize();
simSort(tree);
System.out.println(tree.toString().toString());
}
//Traversing the Tree and Generating Codes
Node oneTree = new Node();
oneTree = tree.get(0);
traverseTree(oneTree);
}
public void simSort(ArrayList<Node> n)
{
for(int i=0;i<n.size()-1;i++)
{
for (int j=0;j<n.size()-1;j++)
{
if(n.get(j).getWeight()<n.get(j+1).getWeight())
{
Node temp = new Node();
temp = n.get(j);
n.set(j, n.get(j+1));
n.set(j+1, temp);
}
}
}
}
public void traverseTree(Node root)
{
Stack nodes = new Stack();
nodes.push(root);
Node currentNode= new Node();
while (! nodes.isEmpty())
{
currentNode = (Node) nodes.pop();
Node right = currentNode.getRight();
if (right != null)
nodes.push(right);
Node left = currentNode.getLeft();
if (left != null)
nodes.push(left);
System.out.println("Node data: "+currentNode.data);
}
}
}
When I run this code it generates the tree but I don't know how to generate the codes using the tree.
Thanks