树的节点定义

public static class Node<E>{
        E Data;// 数据
        int weight; // 权重
        Node leftChild;//左子节点
        Node rightChild;//右子节点

        public Node(E data, int weight) {
            Data = data;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "Data=" + Data +
                    ", weight=" + weight +
                    '}';
        }
    }

树的计算

N个节点的树，有N-1条边

编码问题

字符串编码，可以使得存储控件最小

a b c d e f g

10 15 12 3 4 13 1

实际应用可以进行图片做一些压缩等

哈夫曼树简单实现

package top.zcwfeng.java.arithmetic.huffman;

import java.util.ArrayList;
import java.util.List;

/**
 * 字符 a     b    c    d     e       f  g
 * 频次  10  15  12    3      4      13  1
 * 编码   111 10  00  11011   1100    01  11010
 *
 * 权重路径左都是0，右侧是1
 *   4
 *  / \
 * g1 d3
 * ----------
 *       18
 *      / \
 *     8  a10
 *      / \
 *    e4  4
 *       / \
 *     g1 d3
 * ----------
 *    25
 *   / \
 * c12 f13
 * ----------
 *      33
 *     / \
 *  b15  18
 *      / \
 *     8  a10
 *      / \
 *    e4  4
 *       / \
 *     g1 d3
 *
 * 合并
 *
 *        58
 *       /   \
 *    25       33
 *   / \      / \
 * c12 f13   b15 18
 *          / \
 *         8  a10
 *        / \
 *       e4  4
 *       / \
 *     g1 d3
 *
 * 权重：10×3+15×2+12×2+3×5+4×4+13×2+1×5=146位 最小
 */
public class HuffmanTree {

    public static class Node<E>{
        E Data;// 数据
        int weight; // 权重
        Node leftChild;//左子节点
        Node rightChild;//右子节点

        public Node(E data, int weight) {
            Data = data;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Node{" +
                    "Data=" + Data +
                    ", weight=" + weight +
                    '}';
        }
    }

    public static void main(String[] args) {
        List<Node> nodes = new ArrayList<Node>();
        //节点加入list
        nodes.add(new Node("a",10));
        nodes.add(new Node("b",15));
        nodes.add(new Node("c",12));
        nodes.add(new Node("d",3));
        nodes.add(new Node("e",4));
        nodes.add(new Node("f",13));
        nodes.add(new Node("g",1));
        // 哈夫曼构造
        Node root = createTree(nodes);
        printTree(root);

    }

    /**
     * 构造哈夫曼树
     * @param nodes 节点集合
     * @return 构造出来的哈夫曼树的根节点
     */
    private static Node createTree(List<Node> nodes){
        while (nodes.size() > 1){
            // 生么是最小的，list表进行排序，增序方式，0，1
            sort(nodes);
            Node left = nodes.get(0);//权重最小的
            Node right = nodes.get(1);//权重第二小的
            // 生成一个新的节点（父节点），父节点的权重为两个子节点的和
            Node parent = new Node(null,left.weight+right.weight);
            //树的连接，让子节点和父节点链接
            parent.leftChild = left;
            parent.rightChild = right;
            nodes.remove(0);
            nodes.remove(0);
            nodes.add(parent);
        }
        return nodes.get(0);
    }

    /**
     * 冒泡排序，用于对根节点进行排序（增序排序）
     * @param nodes
     */
    private static void sort(List<Node> nodes) {
        if(nodes.size() <= 1) return;
        for (int i = 0; i < nodes.size(); i++) {
            /*
            从第0个元素开始，依次和后面的比较
            j< array.length-1-i 【array.length-1-i】已经冒泡到了合适位置，可以减少比较次数
             */
            for (int j = 0; j < nodes.size() - 1 - i; j++) {
                if(nodes.get(j+1).weight < nodes.get(j).weight){
                    Node temp = nodes.get(j+1);
                    nodes.set(j+1,nodes.get(j));
                    nodes.set(j,temp);
                }
            }
        }

    }

    /**
     * 打印哈夫曼树(先左子树，再右子树，递归)
     * @param root
     */
    public static void printTree(Node root){
        System.out.println(root.toString());
        if(root.leftChild != null) {
            System.out.print("left:");
            printTree(root.leftChild);
        }
        if(root.rightChild !=null){
            System.out.print("right:");
            printTree(root.rightChild);
        }
    }
}