赫夫曼树：当用 n 个结点（都做叶子结点且都有各自的权值）试图构建一棵树时，如果构建的这棵树的带权路径长度最小，称这棵树为“最优二叉树”，有时也叫“赫夫曼树”或者“哈夫曼树”。
实现步骤：
/** * 节点 */ public class Node implements Comparable<Node> { //节点权值 int value; // 左子节点 Node left; // 右子节点 Node right; public Node(int value) { this.value = value; } /** * 前序遍历 */ public void preOrder() { System.out.println(this); if (this.left!=null) { this.left.preOrder(); } if (this.right!=null) { this.right.preOrder(); } } @Override public int compareTo(Node o) { return this.value - o.value; } @Override public String toString() { return "Node{" + "value=" + value + '}'; } }
import java.util.ArrayList; import java.util.Collections; import java.util.List; public class HuffmanTree { public static void main(String[] args) { int[] arr = {13, 7, 8, 3, 29, 6, 1}; Node huffmanTree = createHuffmanTree(arr); huffmanTree.preOrder(); } public static Node createHuffmanTree(int[] arr) { //遍历数组，数组的每个元素放入Node的集合中，排序 List<Node> nodes=new ArrayList<>(); for (int i = 0; i < arr.length; i++) { nodes.add(new Node(arr[i])); } while (nodes.size()>1){ Collections.sort(nodes); //取出根节点权值最小的两颗二叉树 Node leftNode=nodes.get(0); Node rightNode = nodes.get(1); //构建一颗新的二叉树 Node parent = new Node(leftNode.value + rightNode.value); parent.left=leftNode; parent.right=rightNode; //删除处理过的二叉树 nodes.remove(leftNode); nodes.remove(rightNode); //将新的树加入到node中 nodes.add(parent); } return nodes.get(0); } }
Node{value=67} Node{value=29} Node{value=38} Node{value=15} Node{value=7} Node{value=8} Node{value=23} Node{value=10} Node{value=4} Node{value=1} Node{value=3} Node{value=6} Node{value=13}
