java实现Haffman编码

发布时间:2016-12-31 6:57:03
来源:分享查询网

package com.hjp.huffman;import java.util.*;/** * Created by JiaPeng on 2016/12/28. */public class HuffmanTree {    public static <T> Node<T> createTree(List<Node<T>> nodes) {        while (nodes.size() > 1) {            int nodesLen = nodes.size();            Collections.sort(nodes);            Node<T> left = nodes.get(nodesLen - 1);            Node<T> right = nodes.get(nodesLen - 2);            Node<T> parent = new Node<T>(null, left.getWeight() + right.getWeight());            parent.setLeft(left);            parent.setRight(right);            nodes.remove(left);            nodes.remove(right);            nodes.add(parent);        }        return nodes.get(0);    }    public static <T> List<Node<T>> breath(Node<T> root) {        List<Node<T>> list = new ArrayList<Node<T>>();        Queue<Node<T>> queue = new LinkedList<Node<T>>();        queue.add(root);        StringBuilder stringBuilder = new StringBuilder();        while (!queue.isEmpty()) {            Node<T> pNode = queue.poll();            list.add(pNode);            Node<T> leftNode = pNode.getLeft();            String codeStr = pNode.getCodeStr();            if (leftNode != null) {                if (codeStr != null && !"".equals(codeStr)) {                    leftNode.setCodeStr(codeStr + "0");                } else {                    leftNode.setCodeStr("0");                }                queue.add(leftNode);            }            Node<T> rightNode = pNode.getRight();            if (rightNode != null) {                if (codeStr != null && !"".equals(codeStr)) {                    rightNode.setCodeStr(codeStr + "1");                } else {                    rightNode.setCodeStr("1");                }                queue.add(rightNode);            }

返回顶部
查看电脑版