Java 数据结构（一）

前言

文中链接出处：
1.作者：好记性不如烂本子：https://segmentfault.com/u/jerry0212/articles 个人觉得很详细，值得学习
本文只用来自己学习，并且方便查看使用。

1.定义和基本概念

定义：树是一种非线性的数据结构，由N个结点构成的有限集合。
详细可看：https://segmentfault.com/a/1190000014741176

2.二叉树

度为2的树（树中所有结点中最大的度），子树有左右顺序之分
详细可看：https://segmentfault.com/a/1190000014743964

3.哈夫曼树

例如：假设一段文本，包含58个字符，并且由以下7个字符构成:a,b,c,d,e,f,g；这7个字符出现的频次不同，如何对这7个字符进行编码，使得总编码空间最小？

字符	a	b	c	d	e	f	g
频次	10	15	12	3	4	13	1

【分析】
用等长ASCII编码：58×8=464位；
用等长3位编码：58×3=174位；
用不等长编码：出现频次高的字符用的编码短些，出现频次低的编码长些。
使用二叉树编码:左右分支分别为0,1
如果按照这种方式编码：b 编码 0 f 编码 1 c 编码 10 a 编码 11
那么1101会出现多种编码方式，这样就会产生二义性
那么如何避免二义性？ 字符只在叶节点上（就不会有二义性）

1 0 1 1	f b f f
1 0 1 1	f b a
1 0 1 1	c a

使用哈夫曼编码
构造一颗二叉树，该树的带权路径长度达到最小，成为最优二叉树或者哈夫曼树。
构造方式：
每次把权值最小的两颗二叉树合并；左节点权值比右节点权值小

哈夫曼编码.png

字符	a	b	c	d	e	f	g
频次	10	15	12	3	4	13	1
编码	111	10	00	11011	1100	01	11010

编码长度：
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) {
            super();
            this.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<>();
        //把节点加入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 = HuffmanTree.createTree(nodes);
        printTree(root);
    }

    private static Node createTree(List<Node> nodes) {
        while (nodes.size() > 1) {
            sort(nodes); //进行排序，增序
            Node left = nodes.get(0); //权重最小的
            Node right = nodes.get(1); //第二小的
            //生成父节点，权重为子节点之和，父节点不存数据，所以是null
            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
     */
    public static void sort(List<Node> nodes) {
        if (nodes.size() <= 1) return;
        for (int i = 0; i < nodes.size(); 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);
                }
            }
        }
    }

    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);
        }
    }
}

打印结果：

Node{data=null, weight=58}
leftNode{data=null, weight=25}
leftNode{data=c, weight=12}
rightNode{data=f, weight=13}
rightNode{data=null, weight=33}
leftNode{data=b, weight=15}
rightNode{data=null, weight=18}
leftNode{data=null, weight=8}
leftNode{data=e, weight=4}
rightNode{data=null, weight=4}
leftNode{data=g, weight=1}
rightNode{data=d, weight=3}
rightNode{data=a, weight=10}