美文网首页
Java 数据结构(一)

Java 数据结构(一)

作者: 芳心之纵火犯 | 来源:发表于2019-08-07 16:01 被阅读0次

前言

文中链接出处:
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}

相关文章

  • Java数据结构算法(二)栈和队列

    本文旨作于收集整理使用!! 导航 Java数据结构算法(一)链表 Java数据结构算法(三)树 Java数据结构算...

  • Java(Android)数据结构汇总 -- 总纲

    目录:Java(Android)数据结构汇总(一)-- List(上)Java(Android)数据结构汇总(一)...

  • Java数据结构

    Java 数据结构 Java工具包提供了强大的数据结构。在Java中的数据结构主要包括以下几种接口和类: 枚举(E...

  • Java数据结构算法(五)排序

    算法这点粗略整理一下,后面完善 Java数据结构算法(一)链表 Java数据结构算法(二)栈和队列 Java数据结...

  • java 数据结构(collections)

    JAVA中常用的数据结构(java.util. 中) java中有几种常用的数据结构,主要分为Collection...

  • Java数据结构算法(三)树

    本文旨作于收集整理使用!! 导航 Java数据结构算法(一)链表 Java数据结构算法(二)栈和队列 Java数据...

  • Java数据结构算法(四)图

    本文旨作于收集整理使用!! 导航 Java数据结构算法(一)链表 Java数据结构算法(二)栈和队列 Java数据...

  • 文集总目录

    数据结构 [Java] 目录算法 [Java] 目录LeetCode [Java] 目录设计模式 [Java] 目...

  • Java高级特性-难点汇总

    Java 数据结构(Java 2之前)(高级) Java工具包提供了强大的数据结构,主要是以下几种: 枚举(Enu...

  • Java数据结构和算法

    《Java数据结构和算法》一书,作者Robert Lafore。 1)数据结构算法有什么用? 当你用着java里面...

网友评论

      本文标题:Java 数据结构(一)

      本文链接:https://www.haomeiwen.com/subject/kqzodctx.html