Skip to content

Instantly share code, notes, and snippets.

@AaronC81

AaronC81/HuffmanTree.java

Created May 12, 2019 21:15
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save AaronC81/5448b6c9d177fe30f52951ce749077e7 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save AaronC81/5448b6c9d177fe30f52951ce749077e7 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. AaronC81 created this gist May 12, 2019.
    128 changes: 128 additions & 0 deletions HuffmanTree.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,128 @@
    package huffman;

    import java.util.Map;

    public class HuffmanTree {

    HuffmanTree left, right;
    Character symbol;

    public HuffmanTree() {
    left = null;
    right = null;
    symbol = null;
    }

    /**
    * Convenience method to check if a node has a left branch
    *
    * @return true if the node has a left branch, false otherwise
    */
    private boolean hasLeft() {
    return left != null;
    }

    /**
    * Convenience method to check if a node has a right branch
    *
    * @return true if the node has a right branch, false otherwise
    */
    private boolean hasRight() {
    return left != null;
    }

    /**
    * Convenience method to check if a node is a leaf node.
    *
    * @return true if the node is a leaf node, false otherwise
    */
    private boolean isLeaf() {
    return right == null && left == null;
    }

    /**
    * Check if the tree is empty, i.e. contains no symbols.
    *
    * @return true if the tree is empty, false otherwise
    */
    public boolean isEmpty() {
    return right == null && left == null && symbol == null;
    }

    /**
    * Clear the tree from its content. All symbols are removed from the tree and
    * the tree is then empty.
    */
    public void clear() {
    left = null;
    right = null;
    symbol = null;
    }

    /**
    * Build a Huffman tree from an encoding. The encoding is a Map of the form:
    * {'A':"000",'B':"001",'C':"010",'D':"011",'E':"10",'F':"11"}
    *
    * @param encoding
    */
    public void setCoding(Map<Character, String> encoding) {
    this.clear();
    for (Character key : encoding.keySet()) {
    String code = encoding.get(key);
    System.out.println(code);
    insert(key, code);
    }
    }

    /**
    * Convenience method to insert a symbol into the Huffman tree given a path
    * (e.g. "0010").
    *
    * @param key
    * the symbol to be inserted into the tree
    * @param code
    * the path to insert the symbol into the tree.
    */
    private void insert(Character key, String code) {
    if (isEmpty()) {
    if (!code.isEmpty()) {
    if (code.charAt(0) == '0') { // insert left
    left = new HuffmanTree();
    left.insert(key, code.substring(1));
    } else if (code.charAt(0) == '1') { // insert right
    right = new HuffmanTree();
    right.insert(key, code.substring(1));
    } else { // not binary
    throw new IllegalArgumentException();
    }
    } else { // arrived at a end of coding word and at a leaf
    symbol = key;
    }
    } else {
    if (code.isEmpty()) { // end of coding word but not at a leaf so error
    throw new IllegalArgumentException();
    } else if (code.charAt(0) == '0') { // insert left
    if (hasLeft()) { // branch has been created previously
    left.insert(key, code.substring(1));
    } else { // no branch exists yet
    left = new HuffmanTree();
    left.insert(key, code.substring(1));
    }
    } else if (code.charAt(0) == '1') { // insert right
    if (hasRight()) { // branch has been created previously
    right.insert(key, code.substring(1));
    } else { // no branch exists yet
    right = new HuffmanTree();
    right.insert(key, code.substring(1));
    }
    } else { // not binary
    throw new IllegalArgumentException();
    }
    }

    ////////////////////////////////////////////////////////////
    ///////////////// WRITE YOUR SOLUTION HERE /////////////////
    ////////////////////////////////////////////////////////////

    }
    }