赫夫曼树 订阅
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。 展开全文
给定N个权值作为N个叶子结点,构造一棵二叉树,若该树的带权路径长度达到最小,称这样的二叉树为最优二叉树,也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树,权值较大的结点离根较近。
信息
外文名
Huffman Tree
又    名
最优树
带权路径长度
WPL
中文名
哈夫曼树
路径长度
根结点到第L层结点路径长度为L-1
应    用
哈夫曼编码
哈夫曼树简介
在计算机数据处理中,哈夫曼编码使用变长编码表对源符号(如文件中的一个字母)进行编码,其中变长编码表是通过一种评估来源符号出现机率的方法得到的,出现机率高的字母使用较短的编码,反之出现机率低的则使用较长的编码,这便使编码之后的字符串的平均长度、期望值降低,从而达到无损压缩数据的目的。例如,在英文中,e的出现机率最高,而z的出现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时,e极有可能用一个比特来表示,而z则可能花去25个比特(不是26)。用普通的表示方法时,每个英文字母均占用一个字节,即8个比特。二者相比,e使用了一般编码的1/8的长度,z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算,就可以大幅度提高无损压缩的比例。哈夫曼树又称最优二叉树,是一种带权路径长度最短的二叉树。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的路径长度是从树根到每一结点的路径长度之和,记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。
收起全文
精华内容
下载资源
问答
  • 赫夫曼树

    千次阅读 多人点赞 2019-08-23 11:16:54
    赫夫曼树赫夫曼树:最优二叉树赫夫曼树的构造代码实现 赫夫曼树:最优二叉树 赫夫曼树定义了一个WPL值,这个值等于所有叶子节点的带权路径之和。 例如:下面的三个树,我们可以分别计算出他们的WPL值。 我们可以...

    赫夫曼树:最优二叉树

    赫夫曼树定义了一个WPL值,这个值等于所有叶子节点的带权路径之和。
    例如:下面的三个树,我们可以分别计算出他们的WPL值。
    我们可以看到不同的树结构,对应了不同的WPL值,我们把WPL值最小的树称为赫夫曼树。
    从第二张图,我们可以看出权值越大的节点离根节点越近,越小的节点离根节点越远。
    在这里插入图片描述
    在这里插入图片描述
    在这里插入图片描述

    赫夫曼树的构造

    对于这个数组,我们把它构造成赫夫曼树

    [5,29,7,8,14,23,3,11]
    

    第一步:我们创建节点类,这些值作为节点的权值,存储在集合里。
    在这里插入图片描述

    第二步:将这些节点按照权值的大小进行排序。
    在这里插入图片描述

    第三步:取出权值最小的两个节点,并创建一个新的节点作为这两个节点的父节点,这个父节点的权值为两个子节点的权值之和。将这两个节点分别赋给父节点的左右节点。
    在这里插入图片描述
    第四步:删除这两个节点,将父节点添加进集合里。
    在这里插入图片描述
    第五步:重复第二步到第四步,直到集合中只剩一个元素,结束循环。

    在这里插入图片描述

    代码实现

    package com.wuxudong.HuffmanTree;
    
    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.List;
    
    public class HuffmanTree {
        public static void main(String[] args) {
            int [] arr=new int[]{8,11,23,29,14,7,3,5};
    
            Node node=huffman(arr);
            node.frontShow();
        }
    
        private static Node huffman(int[] arr) {
            //创建一个集合存储二叉数
            List<Node> nodes=new ArrayList<Node>();
    
            for (int value:arr){
                nodes.add(new Node(value));
            }
    
            while (nodes.size()>1) {
                //对集合进行排序
                Collections.sort(nodes);
                //取出最小的节点
                Node left=nodes.get(nodes.size()-1);
    
                //取出次小的节点
                Node right=nodes.get(nodes.size()-2);
    
                //新建一个根节点
                Node parent=new Node(left.value+right.value);
                parent.left=left;
                parent.right=right;
    
                //删除两个节点
                nodes.remove(left);
                nodes.remove(right);
    
                //将根节点添加进集合中
                nodes.add(parent);
    
            }
    
    
            return nodes.get(0);
    
        }
    
    
    }
    
    package com.wuxudong.HuffmanTree;
    
    public class Node implements Comparable<Node>{
        int value;
        Node left;
        Node right;
        public Node(int value){
            this.value=value;
        }
    
        public int compareTo(Node o) {
            return -(this.value-o.value);
        }
    
        @Override
        public String toString() {
            return "Node{" +
                    "value=" + value +
                    '}';
        }
    
        //前序遍历
        public  void frontShow(){
            System.out.println(value);
            if(left!=null){
                left.frontShow();
            }
            if (right!=null){
                right.frontShow();
            }
        }
    }
    
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,829
精华内容 1,931
关键字:

赫夫曼树