蓝桥杯04---Huffuman树

1.问题分析

        哈夫曼树又是最优二叉树，它的度为2（几个孩子），因此可以推算出它的总元素个数为2n-1。用数组法时可以由此确定出初始化元素个数。

        解决方法为：先排序，再选择两个最小的数相加，结果放在队尾，然后删除用掉的这两个数。循环此操作，直至剩下最后一个数即可。

 2.代码实现 2.1数组队列法

import java.util.Arrays;import java.util.Scanner;public class Main { //用队列构造哈夫曼树 public static void main(String[] args) { //1.初始化数组队列，输入数据 Scanner sc=new Scanner(System.in); int n=sc.nextInt();//个数 //哈夫曼树的度为2，加上根节点，所以总数为2n+1 if(n>0&&n<=100){ int[] queueArr=new int[2*n-1]; for(int i=0;i

2.2集合法

import java.util.*;public class Demo22 { public static void main(String[] args) { Scanner sc=new Scanner(System.in); int n=sc.nextInt(); if(n<=100){ List list=new ArrayList(); for(int i=0;i1){ Collections.sort(list); int min1= (int) list.get(0); int min2= (int) list.get(1); list.remove(0); list.remove(0); list.add(min1+min2); sum=sum+min1+min2; } System.out.println(sum); } }}

2.3运行测试

        可见两者运行时间和空间相差不多，论代码量和逻辑思路，还是集合比较方便。

ps:Arrays.sort(queueArr,front,rear+1);参数一为数组名，参数二为起始位置（不含本身），参数为结束位置（含）。