构建哈夫曼树及求它的带权路径长度_哈夫曼树结构和带权路径长度计算_可乐学算法的博客-程序员宅基地

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。要构成哈夫曼树，值比较大的叶子节点高度越低越好。

(1) 将n个权值看出n颗只有根节点的树，构建n颗树。
(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
(3)从森林中删除选取的两棵树，并将新树加入森林；
(4)重复(2)、(3)步n-1遍，最后森林中只有一棵树，这棵树就是哈夫曼树。
(5)直接用递归求它的带权路径长度即可。

java参考代码：


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;

public class Main
{
    
	public static void main(String[] args) 
	{
    
		Scanner sc=new Scanner(System.in);
		int n = sc.nextInt();
		List<Tree> ts=new ArrayList<Tree>();
		//构建n颗只有根节点的树
		for(int i=0;i<n;i++)
			ts.add(new Tree(sc.nextInt()));
		//进行n-1次，删除最小的两棵树，合并两棵树并加进去
		for(int i=0;i<n-1;i++)
			removeAndAdd(ts);
		//求带权路径长度
		int ans=getNum(ts.get(0),0);
		System.out.println(ans);
		
	}
	
	private static int getNum(Tree tree,int n) 
	{
    
		if(tree.left==null&&tree.right==null)
			return tree.data*n;
		return getNum(tree.left, n+1)+getNum(tree.right, n+1);		
	}

	private static void removeAndAdd(List<Tree> ts) 
	{
    
		int min1=Integer.MAX_VALUE;
		int min2=Integer.MAX_VALUE;
		int inx1=-1;
		int inx2=-1;
		//找出两个最小值
		for(int i=0;i<ts.size();i++)
		{
    
			Tree t=ts.get(i);
			if(t.data<min1)
			{
    
				min1=t.data;
				inx1=i;
			}
			else if(t.data<min2)
			{
    
				min2=t.data;
				inx2=i;
			}
		}
		
		//删除两颗最小的数，合并两棵树，并加入
		Tree t1=ts.get(inx1);
		Tree t2=ts.get(inx2);
		Tree t=new Tree(t1.data+t2.data);
		t.left=t1;
		t.right=t2;
		ts.remove(t1);
		ts.remove(t2);
		ts.add(t);
		
	}

	
}

class Tree
{
    
	int data;
	Tree left;
	Tree right;
	Tree(int data) {
    
		super();
		this.data = data;
	}

}

本文链接：https://blog.csdn.net/qq_41022094/article/details/102817189

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

MyBatis-映射器中selectKey标签详解_映射文件中insert的selectkey子元素-程序员宅基地

selectKey用来处理不支持自动生成主键的数据库只能存在于insert或update的子标签中,一般不建议使用.注意selectKey的主要效用并不是用来处理自动生成主键的,其本质作用是:用sql语句来处理,需要特殊处理的表中的列字段,而不是用java代码来处理,以此来减少代码的冗余度.候选属性介绍keyProperty结果集映射目标类的属性;若存在多个,则使用逗号分隔;..._映射文件中insert的selectkey子元素

Celery消息队列----配置定时任务-程序员宅基地

Introduction celery beat is a scheduler; It kicks off tasks at regular intervals, that are then executed by available worker nodes in the cluster.By default the entries are taken from the beat_schedul

linux 同步机制之complete wait_for_completion-程序员宅基地

在Linux内核中，completion是一种简单的同步机制，标志"things may proceed"。要使用completion，必须在文件中包含，同时创建一个类型为struct completion的变量。[cpp] view plaincopy这个变量可以静态地声明和初始化： DECLARE_COMPLETION(my_comp); _wait_for_completion

说实话我只能灌水，我谈技术你们有几个懂的啊？不信？随便发一段我写的代你们有几个能看懂的啊？ -程序员宅基地

说实话我只能灌水，我谈技术你们有几个懂的啊？不信？随便发一段我写的代你们有几个能看懂的啊？视频: 刘德华中国人藏拙贴吧视频音乐了视频发表方法：跟发表图片一样，只要链接是以 .swf 结尾系统就会默认为你发表的是视频了音乐发表方法：跟发表图片一样，只要链接是以 .mp3 或 .wma 结尾系统就会默认为你发表的是音乐了其余的都按照图片方式进行处理相关处理代码 int LinkType

matlab求右特征向量,什么是左右特征向量_?? 1的博客-程序员宅基地

满意答案brxps2017.10.06采纳率：42%等级：8已帮助：509人A=[2 4 6;8 10 12;16 20 10]A =2 4 68 10 1216 20 10>> [x,y]=eig(A)%x为右特征向量，s为左特征向量，v为规格化的左特征向量x =-0.25057066610473 -0.75728611172496 ..._matlab求左右特征向量

Java-文档注释-程序员宅基地

1 Java注释概述 Java的三种注释：（1）单行注释：// 注释内容（2）多行注释：/… 注释内容…./ （3）文档注释：/*.. 注释内容…./ （这种注释可以用来自动地生成文档。在JDK中有个javadoc的工具，可以由源文件生成一个HTML文档。使用这种方式注释源文件的内容，显得很专业，并且可以随着源文件的保存而保存起来。也就是说，当修改源文件时...

随便推点

89/90/91/92/93.JAVA入门__基础知识练习_输入星期数,显示今天的运动计划周一:跑步周二:篮球周三:慢走周四:动感单车周-程序员宅基地

基础知识练习案例：减肥计划输入星期数，显示今天的减肥活动。周一跑步、周二游泳、周三慢走、周四动感单车、周五拳击、周六爬山、周日吃一顿_输入星期数,显示今天的运动计划周一:跑步周二:篮球周三:慢走周四:动感单车周

Wireguard各主流平台的配置教程_wireguard配置-程序员宅基地

WireGuard服务器的建立，可以使用NAS服务器端的Docker容器建立（威联通、群晖、Unraid均可以），或者使用云服务器建立，这里推荐使用腾讯云推出的lighthouse轻量级服务器，新用户65一年还是不错的，这里我选择的操作i系统是“Ubuntu20.04-Docker20”，具体操作可以参考“spoto”大佬的视频，这里就不再赘述。然后在官网下载安卓或者ios安装文件，安装好后，打开WireGuard手机客户端，点击“+”号，选择“扫面二维码”即可。五、Ubuntu客户端的配置。_wireguard配置