public class HuffmanTree implements Comparable{ // name of node (-> char represented by node) public int name; // weight of huffmann-tree public int weight; // right subtree public HuffmanTree right; // left subtree public HuffmanTree left; /** * To construct a new empty HT (subtrees are null and weight is 0). */ public HuffmanTree() { right = null; left = null; weight = 0; } /** * To construct a leaf of the HT with given name (subtrees are empty HTs). * * @param name * name of leaf */ public HuffmanTree(int name) { this.name = name; right = new HuffmanTree(); left = new HuffmanTree(); } /** * To construct a new HT with 2 given subtrees. * * @param left * left subtree * @param right * right subtree */ public HuffmanTree(HuffmanTree left, HuffmanTree right) { // set left subtree this.left = left; // set right subtree this.right = right; // update weight (sum of weights of both subtrees) this.weight = left.weight + right.weight; } /** * To check if HT is empty or not. * * @return true, if both subtrees are null */ public boolean isEmpty() { return left == null && right == null; } /** * To check if HT is a leaf. * * @return true, if actual HT is non-empty, but both subtrees are */ public boolean isLeaf() { return !isEmpty() && left.isEmpty() && right.isEmpty(); } public BitString[] encode(BitString[] codeTable, BitString path) { if (isLeaf()) { codeTable[name] = path; return null; } right.encode(codeTable, path.append(true)); left.encode(codeTable, path.append(false)); return codeTable; } /** * To check if HT is lighter than another one. * * @param tree * other tree to check * @return true, if actual HT is lighter than given HT */ public boolean lighter(HuffmanTree tree) { return this.weight < tree.weight; } public int compareTo(Object o) { HuffmanTree otherTree = (HuffmanTree) o; if (this.weight < otherTree.weight) return -1; else if (this.weight > otherTree.weight) return 1; else return 0; }}