爱华网最优二叉树概念
1．树的路径长度
树的路径长度是从树根到树中每一结点的路径长度之和。在结点数目相同的二叉树中，完全二叉树的路径长度最短。
2．树的带权路径长度(Weighted Path Length of Tree，简记为WPL)
结点的权：在一些应用中，赋予树中结点的一个有某种意义的实数。
结点的带权路径长度：结点到树根之间的路径长度与该结点上权的乘积。
树的带权路径长度(Weighted Path Length ofTree)：定义为树中所有叶结点的带权路径长度之和，通常记为：
其中：
n表示叶子结点的数目
wi和li分别表示叶结点ki的权值和根到结点ki之间的路径长度。
树的带权路径长度亦称为树的代价。
3．最优二叉树或哈夫曼树
在权为wl，w2，…，wn的n个叶子所构成的所有二叉树中，带权路径长度最小(即代价最小)的二叉树称为最优二叉树或哈夫曼树。
【例】给定4个叶子结点a，b，c和d，分别带权7，5，2和4。构造如下图所示的三棵二叉树(还有许多棵)，它们的带权路径长度分别为：
(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最小
public class HuffmanTree{ //内部类Nodepublic static class Node<E>{E data;double weight;Node leftChild;Node rightChild;
public Node(E data, double weight) {this.data = data;this.weight = weight;}
public String toString() {return "Node[data=" + data + ", weight=" + weight + "]";}}
public static void main(String[] args) {List<Node> nodes = newArrayList<Node>();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);PrintTree(root);}
private static Node createTree(List<Node>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);}// 返回nodes集合中唯一的节点，也就是根节点return nodes.get(0);}
// 将指定数组的i和j索引处的元素交换private static voidswap(List<Node> nodes, int i, int j){Node tmp;tmp = nodes.get(i);nodes.set(i, nodes.get(j));nodes.set(j, tmp);}
// 实现快速排序算法，用于对节点进行排序。从大到小的排序private static voidsubSort(List<Node> 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 voidquickSort(List<Node> nodes) {subSort(nodes, 0, nodes.size() - 1);}
//相当于广度优先遍历，分别打印根节点，在打印左右孩子的，按层的public static void PrintTree(Nodenode) {Node left = null;Node right = null;if (node != null) {System.out.print(node.toString());left = node.leftChild;right = node.rightChild;System.out.println("(" + (left != null ?left.toString() : "")+ "," + (right != null ?right.toString() : "") + ")");} //递归打印if (left != null)PrintTree(left);if (right != null)PrintTree(right);}}
