Lacrosse曼树的结构步骤如下所示

 哈弗曼树的构造步骤如下所示

连锁介绍:

 树形结构除了利用于查找和排序等操作时能调高作用,它在信息广播发表领域也存有遍布的应用。福特Explorer曼(Huffman)树就是一种在编码技术方面获得广泛应用的二叉树,它同一时间也是一种最优二叉树。

宝马X3曼树相关的的基本概念:

 为了给出卡宴曼树的概念,从以下多少个基本概念出发并张开描述。

  1. 节点间的门道和节点的路径长度:所谓节点间的路子是指一个节点到另一个节点所经历的节点和分层连串。节点的门径长度是指从根节点到该节点间的路子上的分支数目。

  2. 节点的权和节点的带权路线:在骨子里运用中,大家频仍会给树中的每一种节点赋予叁个有着某种实际意义的数值,这一个数值称为节点的权值。节点的带权路径长度正是该节点的路径长度与该节点的权值的乘积。

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

  4. 最优二叉树:给定n个权值并作为n个叶节点按自然准则组织一棵二叉树,使得其带权路线长度达到最小值,则那棵二叉树被称得上最优二叉树。下图呈现了具有分化带权路线长度的二叉树,个中,第二棵树为最优二叉树

图片 1

中华V曼树和Odyssey曼编码的构造方法

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

 如若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,直到森林中只剩余一棵二叉树停止,则那棵二叉树便是所构成的奔驰G级曼树

下图展现了中华V曼树的构造进程:

图片 2

奥迪Q5曼树构造进度的代码完成

 以下其代码演示了中华V曼树的协会实现在那之中,测量试验代码所用的图如下所示:

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

回到目录|·(工)·)