CR-V曼树

连带介绍:

 树形结构除了采取于查找和排序等操作时能调高功用,它在新闻通信领域也持有广阔的使用。中华V曼(Huffman)树正是壹种在编码本领上边获得广泛应用的二叉树,它同不经常候也是一种最优2叉树。

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

 为了给出Wrangler曼树的定义,从以下多少个基本概念出发并开始展览描述。

  1. 节点间的门道和节点的门道长度:所谓节点间的渠道是指贰个节点到另三个节点所经历的节点和分支体系。节点的路线长度是指从根节点到该节点间的门径上的道岔数目。

  2. 节点的权和节点的带权路径:在事实上行使中,大家往往会给树中的每2个节点赋予1个具备某种实际意义的数值,这些数值称为节点的权值。节点的带权路线长度正是该节点的门道长度与该节点的权值的乘积。

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

  4. 最优二叉树:给定n个权值并视作n个叶节点按一定规则组织一棵2叉树,使得其带权路径长度到达最小值,则那棵2叉树被称呼最优二叉树。下图呈现了有着不一样带权路线长度的二叉树,当中,第1棵树为最优②叉树

图片 1

帕杰罗曼树和卡宴曼编码的构造方法

 瑞虎曼树的结构步骤如下所示:

 假使n个叶节点的权值分别为{w1,w二,…,wn},则

  1. 由已知给定的n个权值{w一,w2,w3,…,wn},构造二个由n棵二叉树所结合的森林F={T一,,T二,T三,…,Tn},当中每一棵2叉树唯有二个根节点,并且根节点的权值分别为w1,w二,….,wn

  2. 在二叉树森林F中采纳根节点的权值最小和次小的两棵二叉树,分别把它们作为左子树和右子树去组织一棵新二叉树,新2叉树的根节点权值为其左、右子树根节点的权值之和

  3. 用作新二叉树的左右子树的两棵贰叉树从森林F中去除。将新发生的二叉树参预到森林F中

  4. 双重步骤二和步子三,直到森林中只剩下1棵2叉树截止,则那棵2叉树就是所组成的HummerH二曼树

下图显示了LX570曼树的结构进度:

图片 2

Rubicon曼树构造进度的代码达成

 以下其代码演示了Highlander曼树的构造完成个中,测试代码所用的图如下所示:

图片 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   

重临目录|·(工)·)

相关文章