如何证明哈夫曼树是最优二叉树_哈夫曼树完全二叉树

如何证明哈夫曼树是最优二叉树_哈夫曼树完全二叉树一、定义一些定义:节点之间的路径长度:在树中从一个结点到另一个结点所经历的分支,构成了这两个结点间的路径上的经过的分支数称为它的路径长度树的路径长度:从树的根节点到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。树的带权路径长度(Weighte…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

一、定义

一些定义:

节点之间的路径长度:在树中从一个结点到另一个结点所经历的分支,构成了这两个结点间的路径上的经过的分支数称为它的路径长度

树的路径长度:从树的根节点到树中每一结点的路径长度之和。在结点数目相同的二叉树中,完全二叉树的路径长度最短。

结点的权:在一些应用中,赋予树中结点的一个有某种意义的实数。

结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。

树的带权路径长度(Weighted Path Length of Tree:WPL):定义为树中所有叶子结点的带权路径长度之和

如下面的二叉树,叶子节点的权值分别为5、6、2、4、7,的带权路径长度计算:

5f9c080f35fce34fcdd206a170e95e3a.png

最优二叉树:从已给出的目标带权结点(单独的结点) 经过一种方式的组合形成一棵树.使树的权值最小.。最优二叉树是带权路径长度最短的二叉树。根据结点的个数,权值的不同,最优二叉树的形状也各不相同。它们的共同点是:带权值的结点都是叶子结点。权值越小的结点,其到根结点的路径越长。

如,给定4个叶子结点a,b,c和d,分别带权7,5,2和4。构造如下图所示的三棵二叉树(还有许多棵),它们的带权路径长度分别为:

1335607635_5879.jpg

(a)WPL=7*2+5*2+2*2+4*2=36

(b)WPL=7*3+5*3+2*1+4*2=46

(c)WPL=7*1+5*2+2*3+4*3=35

其中(c)树的WPL最小,可以验证,它就是哈夫曼树。

注意:

① 叶子上的权值均相同时,完全二叉树一定是最优二叉树,否则完全二叉树不一定是最优二叉树。

② 最优二叉树中,权越大的叶子离根越近。

③ 最优二叉树的形态不唯一,WPL最小。

二、构造哈夫曼树

1) 根据给定的n个权值{w1, w2, w3, w4……wn}构成n棵二叉树的森林 F={T1 , T2 , T3…..Tn},其中每棵二叉树只有一个权值为wi 的根节点,其左右子树都为空;

2) 在森林F中选择两棵根节点的权值最小的二叉树,作为一棵新的二叉树的左右子树,且令新的二叉树的根节点的权值为其左右子树的权值和;

3)从F中删除被选中的那两棵子树,并且把构成的新的二叉树加到F森林中;

4)重复2 ,3 操作,直到森林只含有一棵二叉树为止,此时得到的这棵二叉树就是哈夫曼树。

构造过程如下图:

1-120223213KW27.jpg

三、Java实现

对指定节点创建哈夫曼树:package com.liuhao.DataStructures;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.List;

import java.util.Queue;

public class HuffmanTree {

public static class Node {

E data;

double weight;

Node leftChild;

Node rightChild;

public Node(E data, double weight) {

super();

this.data = data;

this.weight = weight;

}

public String toString() {

return “Node[data=” + data + “, weight=” + weight + “]”;

}

}

public static void main(String[] args) {

List nodes = new ArrayList();

nodes.add(new Node(“A”, 40.0));

nodes.add(new Node(“B”, 8.0));

nodes.add(new Node(“C”, 10.0));

nodes.add(new Node(“D”, 30.0));

nodes.add(new Node(“E”, 10.0));

nodes.add(new Node(“F”, 2.0));

Node root = HuffmanTree.createTree(nodes);

System.out.println(breadthFirst(root));

}

/**

* 构造哈夫曼树

*

* @param nodes

* 节点集合

* @return 构造出来的哈夫曼树的根节点

*/

private static Node createTree(List nodes) {

// 只要nodes数组中还有2个以上的节点

while (nodes.size() > 1) {

quickSort(nodes);

//获取权值最小的两个节点

Node left = nodes.get(nodes.size()-1);

Node right = nodes.get(nodes.size()-2);

//生成新节点,新节点的权值为两个子节点的权值之和

Node parent = new Node(null, left.weight + right.weight);

//让新节点作为两个权值最小节点的父节点

parent.leftChild = left;

parent.rightChild = right;

//删除权值最小的两个节点

nodes.remove(nodes.size()-1);

nodes.remove(nodes.size()-1);

//将新节点加入到集合中

nodes.add(parent);

}

return nodes.get(0);

}

/**

* 将指定集合中的i和j索引处的元素交换

*

* @param nodes

* @param i

* @param j

*/

private static void swap(List nodes, int i, int j) {

Node tmp;

tmp = nodes.get(i);

nodes.set(i, nodes.get(j));

nodes.set(j, tmp);

}

/**

* 实现快速排序算法,用于对节点进行排序

*

* @param nodes

* @param start

* @param end

*/

private static void subSort(List nodes, int start, int end) {

if (start < end) {

// 以第一个元素作为分界值

Node base = nodes.get(start);

// i从左边搜索,搜索大于分界值的元素的索引

int i = start;

// j从右边开始搜索,搜索小于分界值的元素的索引

int j = end + 1;

while (true) {

// 找到大于分界值的元素的索引,或者i已经到了end处

while (i < end && nodes.get(++i).weight >= base.weight)

;

// 找到小于分界值的元素的索引,或者j已经到了start处

while (j > start && nodes.get(–j).weight <= base.weight)

;

if (i < j) {

swap(nodes, i, j);

} else {

break;

}

}

swap(nodes, start, j);

//递归左边子序列

subSort(nodes, start, j – 1);

//递归右边子序列

subSort(nodes, j + 1, end);

}

}

public static void quickSort(List nodes){

subSort(nodes, 0, nodes.size()-1);

}

//广度优先遍历

public static List breadthFirst(Node root){

Queue queue = new ArrayDeque();

List list = new ArrayList();

if(root!=null){

//将根元素加入“队列”

queue.offer(root);

}

while(!queue.isEmpty()){

//将该队列的“队尾”元素加入到list中

list.add(queue.peek());

Node p = queue.poll();

//如果左子节点不为null,将它加入到队列

if(p.leftChild != null){

queue.offer(p.leftChild);

}

//如果右子节点不为null,将它加入到队列

if(p.rightChild != null){

queue.offer(p.rightChild);

}

}

return list;

}

}以上代码中的关键步骤包括:

(1)对list集合中所有节点进行排序;

(2)找出list集合中权值最小的两个节点;

(3)以权值最小的两个节点作为子节点创建新节点;

(4)从list集合中删除权值最小的两个节点,将新节点添加到list集合中

程序采用循环不断地执行上面的步骤,直到list集合中只剩下一个节点,最后剩下的这个节点就是哈夫曼树的根节点

四、哈夫曼编码

根据哈夫曼树可以解决报文编码的问题。假设需要把一个字符串,如“abcdabcaba”进行编码,将它转换为唯一的二进制码,但是要求转换出来的二进制码的长度最小。

假设每个字符在字符串中出现频率为W,其编码长度为L,编码字符n个,则编码后二进制码的总长度为W1L1+W2L2+…+WnLn,这恰好是哈夫曼树的处理原则。因此可以采用哈夫曼树的构造原理进行二进制编码,从而使得电文长度最短。

对于“abcdabcaba”,共有a、b、c、d4个字符,出现次数分别为4、3、2、1,相当于它们的权值,将a、b、c、d以出现次数为权值构造哈夫曼树,得到下左图的结果。

从哈夫曼树根节点开始,对左子树分配代码“0”,对右子树分配“1”,一直到达叶子节点。然后,将从树根沿着每条路径到达叶子节点的代码排列起来,便得到每个叶子节点的哈夫曼编码,如下右图。

2d4e2b172c055cd4934686d8d2bec3cb.png

从图中可以看出,a、b、c、d对应的编码分别为0、10、110、111,然后将字符串“abcdabcaba”转换为对应的二进制码就是0101101110101100100,长度仅为19。这也就是最短二进制编码,也称为哈夫曼编码。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/219620.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • IntelliJ IDEA集成svn

    IntelliJ IDEA集成svnEclipse集成svn相信大家已经非常熟悉了,但是IntelliJIDEA如何集成svn呢?下面简单介绍一下(其他的版本控制工具的集成类似):1.首先配置下载并配置svn软件,推荐使用SlikSvn。2.在IntelliJIDEA集成svn,选择Subversion。3.配置完成之后就可以从svn服务器上checkout代码。4.修改代码之后,在该文件或

    2022年10月18日
  • chrome加载慢_多线程有什么用

    chrome加载慢_多线程有什么用谷歌浏览器采用的是单线程下载,想要提高下载速度,就得采用多线程的下载方式,Chrome默认还是单线程下载,如果想要谷歌多线程下载,就要手动开启,下面听MacW小编娓娓道来,介绍如何开启Chrome多线程下载!先来看看开启前的下载速度,(同一个文件)看到了吧!默认情况下,只有左右,远没有到达带宽的上限,接下来跟着小编一起开启这个隐藏的功能,国产Chrome内核的浏览器通通适用,包括前段时间推送的新版Edge也可以。chrome://flags/#enable-parallel-downloading

  • 为什么会有内存屏障呢_内存出问题有什么现象

    为什么会有内存屏障呢_内存出问题有什么现象复习一下内存屏障主要解决指令重排和可见性,需要了解JMM架构原文链接为什么会有内存屏障每个CPU都会有自己的缓存(有的甚至L1,L2,L3),缓存的目的就是为了提高性能,避免每次都要向内存取。但是这样的弊端也很明显:不能实时的和内存发生信息交换,分在不同CPU执行的不同线程对同一个变量的缓存值不同。用volatile关键字修饰变量可以解决上述问题,那么volatile是如何做到这一点的呢?那就是内存屏障,内存屏障是硬件层的概念,不同的硬件平台实现内存屏障的手段并不是一样,java通过屏蔽这些差异,统

  • 学习方法——哈佛大学幸福课(积极心理学)学习笔记(下)[通俗易懂]

    学习方法——哈佛大学幸福课(积极心理学)学习笔记(下)[通俗易懂]最近刚看完哈佛大学的幸福课(又名积极心理学),真的是受益匪浅,通常心理学只研究如何消除抑郁、自卑等消极心理,但是消除了消极心理并不代表就会变得幸福,就像摆脱了痛苦并不代表获得了快乐。积极心理学的核心内容就是去分析积极心理的特点、研究如何培养他们。下面目录中加粗的章节是我认为的讲的最好的章节,从根源去分析悲观、焦虑以及完美主义等是如何产生的,然后分析它们与积极品性的关系,最后告诉我们培养积极品性…

  • 学习笔记-正则表达式[通俗易懂]

    学习笔记-正则表达式[通俗易懂]学习笔记-正则表达式

  • D3DXMatrixMultiply 函数

    D3DXMatrixMultiply 函数

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号