Atividade 07 - TAP II

import java.util.ArrayList;
import java.util.Collections;

public class MainCls {

    /**
     * Função para transformar a String em um vetor com a quantidade de cada
     * caracter correspondente a tabela ASCII
     *
     * @param txt
     *            String que será aplicada o Huffman, passada pelo usuário
     * @return Vetor da tabela ASCII contendo a quantidade de cada caracter na
     *         String em sua respectiva posição
     */
    public static int[] frequencia(String txt) {
        int vet[] = new int[256];

        for (int i = 0; i < txt.length(); i++) {
            char ch = txt.charAt(i);
            vet[ch]++;
        }
        return vet;
    }

    /**
     * Função para imprimir o código Huffman de cada caracter
     *
     * @param no
     *            Nó raiz da árvore
     */
    public static void preOrdem(Node<Integer> no) {
        // Condição de parada
        if (no == null)
            return;
        // 1) Tratar raiz
        // Se o valor da esquerda e direita forem nulos
        if (no.getEsq() == null && no.getDir() == null) {
            // Imprimimos o caracter, sua quantidade e seu código Huffman
            System.out.println("  " + no.getSimbolo() + "  \t  " + no.getQtd()
                    + "\t " + no.getAux());
        }
        // 2) Percorrer sae
        // Se o nó esquerdo não for nulo
        if (no.getEsq() != null) {
            // Adicionamos o auxiliar 0 junto ao auxiliar do seu pai
            no.getEsq().setAux(no.getAux() + "0");
            // Chamamos a função novamente passando o nó esquerdo como
            // referência
            preOrdem(no.getEsq());
        }

        // 3) Percorrer sad
        // Se o nó direito não for nulo
        if (no.getDir() != null) {
            // Adicionamos o auxiliar 1 junto ao auxiliar do seu pai
            no.getDir().setAux(no.getAux() + "1");
            // Chamamos a função novamente passando o nó direito como
            // referência
            preOrdem(no.getDir());
        }
    }

    public static void main(String[] args) {
        // Lista para armazenar a árvore
        ArrayList<Node> lista = new ArrayList<Node>();
        // String informada pelo usuário
        String texto = "DCCACADEACCCCCBCEBBBD";

        // Passamos a string para a função que nos retornará a frequência e
        // armazenamos em outro vetor
        int freq[] = frequencia(texto);

        // Percorremos o vetor frequência
        for (int i = 0; i < freq.length; i++) {
            // Caso não seja igual a zero é porque existe uma quantidade de
            // caracter correspondente a posição da tabela ASCII
            if (freq[i] != 0) {
                // Criamos um novo nó
                Node n = new Node();
                // Setamos o caracter como simbolo
                n.setSimbolo((char) i);
                // Setamos a quantidade como frequência
                n.setQtd(freq[i]);
                // Adicionamos o nó na lista
                lista.add(n);
            }
        }

        // Devemos reduzir a lista à apenas um nó
        while (lista.size() > 1) {
            // Ordenamos a lista de forma crescente
            Collections.sort(lista);
            // Removemos o primeiro e segundo elemento da lista armazenando cada
            // um em um nó
            Node n1 = lista.remove(0);
            Node n2 = lista.remove(0);
            // Criamos um novo nó
            Node novo = new Node();
            // O nó esquerdo ao novo nó deverá ser o primeiro elemento retirado
            // da lista
            novo.setEsq(n1);
            // O nó direito ao novo nó deverá ser o segundo elemento retirado
            // da lista
            novo.setDir(n2);
            // O novo nó irá conter a soma da frequência de seus dois filhos
            novo.setQtd(n1.getQtd() + n2.getQtd());
            // Adcionamos o novo nó na lista
            lista.add(novo);
            // O bit da raiz é vazio, pois não tem nenhum caracter nele
            novo.setAux("");
        }
        // Imprimimos a tabela com o caracter, frequência e seus bits
        System.out.println("Simbolo  Qtd     bits");
        // Chamamos a função para imprimir
        preOrdem(lista.get(0));

    }
}

#########################################

/**
 * Classe nó para criar e gerenciar a árvore
 */
public class Node<E> implements Comparable<Node> {
    private Character simbolo;
    private int qtd;
    private Node esq, dir;
    private String aux;

    public String getAux() {
        return aux;
    }

    public void setAux(String aux) {
        this.aux = aux;
    }

    public Character getSimbolo() {
        return simbolo;
    }

    public void setSimbolo(Character simbolo) {
        this.simbolo = simbolo;
    }

    public int getQtd() {
        return qtd;
    }

    public void setQtd(int qtd) {
        this.qtd = qtd;
    }

    public Node getEsq() {
        return esq;
    }

    public void setEsq(Node esq) {
        this.esq = esq;
    }

    public Node getDir() {
        return dir;
    }

    public void setDir(Node dir) {
        this.dir = dir;
    }

    @Override
    public int compareTo(Node o) {
        if (qtd > o.getQtd())
            return 1;
        else if (qtd < o.getQtd())
            return -1;
        else
            return 0;
    }

}