当前位置:澳门新萄京网址 > 澳门新萄京网址 > 哈弗曼树

哈弗曼树

文章作者:澳门新萄京网址 上传时间:2019-11-18

相关介绍:

 树形结构除了利用于查找和排序等操作时能调高功能,它在音信简报领域也可以有着分布的选择。汉兰达曼(Huffman)树正是生龙活虎种在编码技能方面拿到普遍应用的二叉树,它同一时间也是生机勃勃种最优二叉树。

Qashqai曼树相关的的基本概念:

 为了给出讴歌RDX曼树的概念,从以下几个基本概念出发并开展描述。

  1. 节点间的门路和节点的渠道长度:所谓节点间的门道是指四个节点到另一个节点所经验的节点和支行种类。节点的门路长度是指从根节点到该节点间的不二等秘书诀上的分层数目。

  2. 节点的权和节点的带权路线:在其实应用中,大家往往会给树中的每二个节点授予三个具有某种实际意义的数值,这些数值称为节点的权值。节点的带权路线长度正是该节点的门径长度与该节点的权值的乘积。

  3. 树的带权路线长度:树的带权路线长度正是树中具有叶节点的带权路线长度之和,经常记为:(WPL=sum_{i=1}^{n}W_{i} times L_{i})当中,n为叶节点的个数,(W_{i})为第i个叶节点的权值,(L_{i})为第i个叶节点的路子长度

  4. 最优二叉树:给定n个权值并作为n个叶节点按自然准则协会后生可畏棵二叉树,使得其带权路线长度达到最小值,则那棵二叉树被称呼最优二叉树。下图彰显了有着区别带权路线长度的二叉树,在那之中,第二棵树为最优二叉树

图片 1

索罗德曼树和Tiggo曼编码的构造方法

 奥迪Q7曼树的布局步骤如下所示:

 借使n个叶节点的权值分别为{w1,w2,...,wn},则

  1. 由已知给定的n个权值{w1,w2,w3,...,wn},构造三个由n棵二叉树所构成的森林F={T1,,T2,T3,...,Tn},个中每风度翩翩棵二叉树唯有三个根节点,並且根节点的权值分别为w1,w2,....,wn

  2. 在二叉树森林F中甄选根节点的权值最小和次小的两棵二叉树,分别把它们当作左子树和右子树去协会生龙活虎棵新二叉树,新二叉树的根节点权值为其左、右子树根节点的权值之和

  3. 作为新二叉树的左右子树的两棵二叉树从森林F中删除。将新爆发的二叉树参预到森林F中

  4. 重复步骤2和步子3,直到森林中只剩下风流倜傥棵二叉树停止,则这棵二叉树便是所组成的LX570曼树

下图显示了凯雷德曼树的组织进程:

图片 2

奥迪Q7曼树构造进程的代码完成

 以下其代码演示了科雷傲曼树的结构完毕在那之中,测量试验代码所用的图如下所示:

图片 3

连锁代码:

package all_in_tree;

import java.util.Comparator;
import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 该类用于演示哈弗曼树的构造过程
 * @author 学徒
 *
 */
public class Huffman
{
    //哈弗曼树的根节点
    private HuffmanNode root;
    //一个优先级队列,确保每次取出的均为节点中其权值最小的节点
    private Queue<HuffmanNode> q;
    /**
     * 用于初始化,其优先队列
     */
    public Huffman()
    {
        Comparator<HuffmanNode> cmp=new Comparator<HuffmanNode>()
        {
                @Override
                public int compare(HuffmanNode obj1,HuffmanNode obj2)
                {
                    int obj1Number=obj1.weight;
                    int obj2Number=obj2.weight;
                    if(obj1Number>obj2Number)
                        return 1;
                    else if(obj1Number<obj2Number)
                        return -1;
                    else
                        return 0;
                }
        };
        q=new PriorityQueue<HuffmanNode>(11,cmp);
    }
    /**
     * 用于添加节点到优先队列中,进行哈弗曼树的构造
     * @param node
     */
    public void addHuffmanNode(HuffmanNode node)
    {
        q.add(node);
    }
    /**
     * 用于构造哈弗曼树
     */
    public HuffmanNode createHuffmanTree()
    {
        while(!q.isEmpty()&&q.size()>=2)
        {
            HuffmanNode node1=q.poll();
            HuffmanNode node2=q.poll();
            HuffmanNode newNode=new HuffmanNode();
            newNode.weight=node1.weight+node2.weight;
            newNode.left=node1;
            newNode.right=node2;
            q.add(newNode);
        }
        if(!q.isEmpty())
            this.root=q.poll();
        return this.root;
    }
    /**
     * 用于测试相关的代码
     */
    public static void main(String[] args)
    {
        Huffman tree=new Huffman();
        for(int i=0;i<5;i++)
        {
            tree.addHuffmanNode(new HuffmanNode((char)('A'+i),i+1));
        }
        HuffmanNode root=tree.createHuffmanTree();
        System.out.println("其最高顶点的权值"+root.weight);
        //对该哈弗曼树进行层次遍历
        Queue<HuffmanNode> q=new LinkedList<HuffmanNode>();
        q.add(root);
        while(!q.isEmpty())
        {
            HuffmanNode node=q.poll();
            System.out.print(node.weight+"t");
            if(node.left!=null)
                q.add(node.left);
            if(node.right!=null)
                q.add(node.right);
        }
    }
}
/**
 * 用于创建哈弗曼树的节点类的描述
 * @author 学徒
 *
 */
class HuffmanNode
{
    //用于存放相关的数据
    Object data;
    //用于记录该节点的权
    int weight;
    //该节点的左孩子
    HuffmanNode left;
    //该节点的右孩子
    HuffmanNode right;
    public HuffmanNode()
    {
    }
    public HuffmanNode(Object data,int weight)
    {
        this.data=data;
        this.weight=weight;
    }
}

运行结果:

其最高顶点的权值15
15  6   9   3   3   4   5   1   2   

回到目录|·(工)·卡塔 尔(阿拉伯语:قطر‎

本文由澳门新萄京网址发布于澳门新萄京网址,转载请注明出处:哈弗曼树

关键词: