将一串数字转换为哈夫曼树的方法如下:首先把数组排序,每次取出两个最小数字节点,并将其组成一个新的二叉树,该二叉树的根是取出的两个节点的和,合并后将这两个节点移除,使用合并后的节点代替,再次排序,重复上述,即可得到WPL树。
代码实现如下
首先创建节点类,为了方便,将每一个节点存储到一个ArrayList中,并实现Comparable接口,方便后面使用自带的排序方法。package 赫夫曼树; public class HuffmanTreeNode implements Comparable生成哈夫曼树的方法,并实现前序遍历方便演示{ int value; HuffmanTreeNode leftNode; HuffmanTreeNode rightNode; public HuffmanTreeNode(int value) { this.value = value; } @Override public int compareTo(HuffmanTreeNode huffmanTreeNode) { return this.value - huffmanTreeNode.value; } }
package 赫夫曼树; import 二叉树.BinaryTreeNode; import java.util.ArrayList; import java.util.Collection; import java.util.Collections; public class GenerateHuffmanTree { public static HuffmanTreeNode HuffmanTree(int[] arr) { ArrayList测试:arrayList = new ArrayList<>(); for (int i = 0; i < arr.length; i++) { arrayList.add(new HuffmanTreeNode(arr[i])); } while (arrayList.size() > 1) {//只要数组大小不为1,就继续合并 Collections.sort(arrayList);//首先进行排序 HuffmanTreeNode small = arrayList.get(0); HuffmanTreeNode bigger = arrayList.get(1);//取出前两个最小的值 HuffmanTreeNode sum = new HuffmanTreeNode(small.value + bigger.value); //创建一个新树节点,其值为二者之和,左树为较小的那一个,右树为较大的那一个 sum.leftNode = small; sum.rightNode = bigger; arrayList.remove(small); arrayList.remove(bigger);//二者被合并后将其从数组中移除 arrayList.add(sum);//添加合并后的树到数组 } return arrayList.get(0); } public static void PreOrdered(HuffmanTreeNode root) { if (root != null) { System.out.print(root.value + " "); PreOrdered(root.leftNode); PreOrdered(root.rightNode); } } }
public static void main(String[] args) { int[] arr = new int[]{3,8,7,2,5}; HuffmanTreeNode huffmanTreeNode = GenerateHuffmanTree.HuffmanTree(arr); GenerateHuffmanTree.PreOrdered(huffmanTreeNode); }
结果:67 29 38 15 7 8 23 10 4 1 3 6 13
Process finished with exit code 0