thank

前几天上课讲了huffmanTree树的实现原理
现在有空就用代码简单实现一遍

首先解释一遍实现huffmanTree基本思想
1 将所有节点存入一个数组/链表中,从中找出两个最小值,并且组成一个新节点
2 将上述中的两个最小值删除,将新节点加入数组/链表中
3 重复1-2步骤,直到数组/链表剩下1个节点

定义一下Node节点属性
String data 存放数据,可以使用泛型
int weight 权重
Node leftNode 左节点
Node rightNode 右节点
String encode 编码

构造huffmanTree

/**
 *
 * @param nodeList  存入一个node链表
 * @return          根节点
 */
public Node create(LinkedList<Node> nodeList){

    int len = nodeList.size();
    Collections.sort(nodeList);


    for (int i = 1; i < len; i++){

        int index = 0;
        Node node1 = nodeList.remove(0);
        Node node2 = nodeList.remove(0);


        int newNodeWeight = node1.getWeight() + node2.getWeight();
        Node newnode = new Node(newNodeWeight);
        newnode.setLeftNode(node1);
        newnode.setRightNode(node2);
        newnode.setData("父节点");

        while (true){
            if (index == nodeList.size() || newnode.getWeight() < nodeList.get(index).getWeight()){
                nodeList.add(index,newnode);
                break;
            }
            index++;
        }

    }

    return nodeList.get(0);

}

算法的思想:

先进行一遍排序,自然最小的两个数在0,1两个位置,删除头两个Node节点,并组成一个新节点,再用新节点从头开始比较,遇到比它大的数就停下来,自然也是有序的,最后返回一个根节点,就可以通过根节点对其他节点进行编码;

对节点进行编码很简单,定义一下编码,记向左为0,向右为1,一直递归到左右都没有节点

/**
 *
 * @param node          根节点
 * @param leftcode      左节点编码
 * @param rightcode     右节点编码
 * @param code          初始的编码
 */
public void encode(Node node, String leftcode, String rightcode, String code){
    if (node.getLeftNode() != null){
        String temp = code + leftcode;
        encode(node.getLeftNode(), leftcode, rightcode, temp);
    }

    if (node.getRightNode() != null){
        String temp = code + rightcode;
        encode(node.getRightNode(), leftcode, rightcode, temp);
    }

    if (node.getLeftNode() == null || node.getRightNode() == null){
        node.setEncode(code);
    }


}

最后再打印一下节点

/**
 *
 * @param root 树的根节点
 */
public void printAllNode(Node root){
    //先序遍历
    System.out.println(root.getData() + " -> " + root.getEncode());
    if (root.getLeftNode() != null){
        printAllNode(root.getLeftNode());
    }
    if (root.getRightNode() != null){
        printAllNode(root.getRightNode());
    }

}