您的位置: 首页  >  文章  >  哈夫曼树和哈夫曼编码

哈夫曼树和哈夫曼编码

分类: 文章 • 2024-12-12 16:38:40

哈夫曼树和哈夫曼编码

二叉树及二叉树的遍历

二叉树，从名字上就能理解，两个叉的树，每个父节点只有左子节点和右子节点。

哈夫曼树和哈夫曼编码

  • 关于二叉树的遍历：先序遍历，中序遍历，后序遍历。

    这里的先序中序后序号指的是父节点的输出顺序，因为哈夫曼树构造出来想要输出树来看整棵树的结构，所以先把二叉树的遍历来写一遍。

    iterator (Tree root){
    if tree == null 
        return
    // print(tree.val) 输出语句在这里代表先序遍历
    if  tree.left != null
        iterator(tree.left)
    // print(tree.val) 输出语句在这里代表中序遍历
    if tree.right != null
        iterator(tree.right)
    // print(tree.val) 输出语句在这里代表后序遍历
}

哈夫曼树介绍

最优

哈夫曼树是一棵最优二叉树，怎么个最优，可以看下面这个例子。

要对同学们的期末考试成绩进行ABCDE五个等级划分:

[100,90] – A (90,80] – B (80,70] – C (70,60] – D (60,0] --E

我们可以先来假设一下：一共有100名同学们的成绩8名同学为等级A, 25名同学成绩等级为B, 40名同学等级C， 15名同学成绩为D，12名同学成绩为E。

可以这样比较：

哈夫曼树和哈夫曼编码

计算一下用这个比较过程算完所有同学的成绩等级所需要的比较次数：**8×1+25×2+40×3+15×4+12×5 = 298 **

再看下面这个比较过程：

哈夫曼树和哈夫曼编码

可以再计算一下新的比较过程所需要比较的总次数：1×40+2×25+3×15+4×(12+8) = 215

可以发现，第二个比较过程比较的次数明显小于第一个，第二个比较过程就是一棵最优二叉树，也就是哈夫曼树。

哈夫曼树

哈夫曼树，又称为最优二叉树，是指对于一组带有确定权值的叶子结点所构造的具有带权路径长度最短的二叉树。在上面的例子里每个成绩等级就是叶子结点，而每个等级的人数又是叶子结点所带有的权值，而最后所求的总比较次数就是带权路径长度。

二叉树的路径长度是指由根节点到所有叶子结点的路径长度之和。可以由下面的公式来表示：
WPL=∑i=0nVi×Li WPL = \sum_{i=0}^n{V_i×L_i}
n代表叶子节点的个数，V代表叶子节点，L代表叶子节点的路径长度，i表示第i个叶子节点。

也就是，当某棵树的WPL值最小，那么这棵树就是最优二叉树，也就是哈夫曼树。哈夫曼树可以有多棵，但是最小WPL值只有一个。

哈夫曼树构造过程

那应该怎样构造一棵哈夫曼树呢。可以发现，在哈夫曼树中，权值越大的叶子节点里根节点越近，那这就代表要有一个优先顺序，考虑先对字符集按照权值大小排序。按照从小到大的顺序排好之后，把每一个字符当成一棵独立的树，开始构造哈夫曼树，从底向上的来构造，先将权值最小的两个节点分别作为左子树和右子树来构造成一棵小的树，构造成的父节点的权值即两个子节点的权值之和。然后将两个子节点在字符集中删除，将它们的父节点放入其中，还是按照权值大小调整好顺序。再接着取两个最小权值节点进行构造成小树，生成新的节点，删除旧的节点，重复上述步骤，直到集合里只剩下一棵树为止。

算法简单描述 + 伪代码

  1. 在含有n个字符的字符集中，将每一个字符及其权值作为一棵单独的无子节点的树。构成一个树集合 。并将所有的子树按照权值大小升序排序。
  2. 取权值最小的前两棵树出来，分别作为左右节点构造新树，所构造的树的父节点权值为子节点权值之和。
  3. 将新树放回集合，将刚刚构造新树的子树在集合中删除掉，调整集合顺序。
  4. 重复步骤2步骤3,直到集合中只有一棵树。
mkHuffman(treeList){
    sort(treeList);//对树集合按照节点的权值排序
    while(treeList.size > 1){
        Tree newTree;
        newTree.left = treeList[0]; //左子树
        newTree.left = treeList[1]; //右子树
        newTree.left.w = treeList[0].w+treeList[1].w; // 新树的权值，w表示权值
        treeList.remove(0); //删除左右子树 添加新的树
        treeList.remove(1);
        treeList.add(newTree);
    }
    huffmanTree = treeList[0];//哈夫曼树
}

算法时间复杂度

最优的排序时间复杂度为O(nlogn)，我自己在写的时候使用的堆排序，因为堆比较容易维护堆顶一直为最小节点，时间复杂度O(nlogn)。

构造树的过程时间复杂度为O(n),也就是挨个的把每个节点都取出来然后构造树。

哈夫曼编码

编码

哈夫曼编码是哈夫曼树的一个应用，当构造出来一棵哈夫曼树，可以对其中的叶子节点进行编码。比如这棵树：

哈夫曼树和哈夫曼编码

这棵哈夫曼树有ABCD四个节点，规定每个根节点的左子树分支用0表示，右子树分支用1表示。这样，所有叶子节点的哈夫曼编码可以表示为：

A:111	B:10	C:110	D:0

这样在通信的时候就可以用哈夫曼编码来代替字符。

关于最优前缀码：

先说什么是前缀码：

所谓前缀码是指，对字符集进行编码的时候，要求字符集中任意一字符的编码都不是其它字符的编码前缀。

比如02,023,10,01,111就不是前缀码，因为编码02为编码023的前缀码。哈夫曼编码就是一种前缀码。

再说最优前缀码：

最优前缀码是指，平均码长 或 文件总长最小 的前缀编码成为最优的前缀码。

这个最优和最优二叉树里的最优是一个意思，也就是说在发送的文件里面，出现频率高的字符所对应的前缀码要尽可能的短，这样我们整个文件的前缀码长度才会达到最短，这个前缀码也就是最优前缀码了。

解码

因为哈夫曼编码为前缀码，这就代表着一段编码只能解码出来一个对应的字符串，不会有任何冲突，用一串编码对照着哈夫曼树，从根节点开始，遇0向左子树方向走，遇1向右子树方向走，走到叶节点输出字符，重新从根节点开始。

比如 111101100 这串编码在上图解码结果就是：ABCD

总代码

用java实现的huffman树构造，编码及解码。首先有一个TreeNode类，用来实现树，树集合用的优先队列，方便排序。

//TreeNode
public class TreeNode {

    public int val; // 每个节点的权重
    public String strVal; // 每个节点所代表的字符
    public TreeNode left;
    public TreeNode right;
    
    public TreeNode (String strVal,int x){
        this.strVal = strVal;
        val = x;
    }
}

    //huffman树的构造函数
	public static void mkHuffmanTree(String[] strings, int[]  w){
        // 所有节点和其权值 将节点按权值从小到大排序放入堆中
        PriorityQueue<TreeNode> pq = new PriorityQueue<>(new Comparator<TreeNode>() {
            @Override
            public int compare(TreeNode o1, TreeNode o2) {
                return o1.val - o2.val;
            }
        });
        
        for (int i = 0; i < strings.length; i++) 
            pq.add(new TreeNode(strings[i],w[i]));
       
        // 取最小的两个节点构建树
        while(pq.size() > 1){
            TreeNode leftNode = pq.poll();
            TreeNode rightNode = pq.poll();
            TreeNode node = new TreeNode("*",leftNode.val+rightNode.val);
            node.right = rightNode;
            node.left = leftNode;
            pq.add(node);
        }

        TreeNode treeNode = pq.poll();
    }

	// 二叉树中序遍历函数
    public static void iterator(TreeNode node){
        if (node == null) return;
        
        if (node.left != null) iterator(node.left);

        System.out.println(node.val);

        if (node.right != null) iterator(node.right);

    }

    //哈夫曼编码：
    public static void huffmanCoding(TreeNode node, String path){
        if (node == null) return;
        if (node.left == null && node.right == null)
            System.out.print(node.strVal+" "+node.val+" "+path+"   ");
        
        if (node.left != null)
            huffmanCoding(node.left,path+"0");
        
        if (node.right != null)
            huffmanCoding(node.right,path+"1");

    }

    //哈夫曼解码函数
    public static void huffmanEncoding(String coding, TreeNode node){
        TreeNode root = node;
        for(char c : (coding+"*").toCharArray()){
            if (root.left == null) {
                System.out.print(root.strVal+" ");
                root = node;
            }
            if (c == '0') root = root.left;
            else root = root.right;
        }
    }

相关推荐