数据结构与算法14 – 树的应用

 
 
OptimalBinaryTree.java

/**
 * @Classname OptimalBinaryTree
 * @Description
 * @Date 2020/4/13 10:48
 * @Created by lrc
 */
public class OptimalBinaryTree<T> {

    //二叉树根节点 - 根据datas进行组建
    Node<T> root;

    //构造器传入的数据
    T[] datas;


    //传数组构造最优二叉树
    OptimalBinaryTree(@NotNull T...datas) {


        T[] copyData = Arrays.copyOf(datas, datas.length);
        Arrays.sort(copyData);
//        System.out.println(Arrays.toString(copyData));
        datas = copyData;

        createdOptimalBinaryTree(datas);

    }


    public Node<T> getRoot() {
        return root;
    }

    // 最优二叉树 - 中序遍历
    public String  inOrder() {

        StringBuilder sb = new StringBuilder();

        sb.append("[");

        //真正的中序遍历
        root.inOrder(root,sb);

        sb.replace(sb.lastIndexOf(", "), sb.length(), "");

        sb.append("]");

        return sb.toString();


    }


    // 最优二叉树 - 前序遍历
    public String  preOrder() {

        StringBuilder sb = new StringBuilder();

        sb.append("[");

        //真正的前序遍历
        root.preOrder(root,sb);

        sb.replace(sb.lastIndexOf(", "), sb.length(), "");

        sb.append("]");

        return sb.toString();


    }


    @Override
    public String toString() {
        return preOrder();
    }

    private boolean createdOptimalBinaryTree(T[] datas) {

        LinkedList<Node<T>> list = new LinkedList<>();

        boolean flag = false;

        Node<T> newNode;
        for(T data : datas) {
            newNode = new Node<>();
            newNode.setData(data);
            list.add( newNode );
        }


        while(true) {

            //弹出两个子节点，构成左右子树
            Node<T> lNode = list.pop();
            Node<T> rNode = list.pop();

            //父节点权重是上面两个子节点的权重
            Node<T> parNode = new Node<>();
            parNode.weight = lNode.weight + rNode.weight;
            parNode.leftNode = lNode;
            parNode.rightNode = rNode;

            //父节点必须往链表头添加 - 否则遇到weigth相同时，组件二叉树会混乱
            list.addFirst(parNode);
            Collections.sort(list);

            //打印当前链表情况
//            System.out.println("遍历" + list);

            //如果链表中只有一个元素，说明这个节点就是根节点
            if(list.size() == 1) {
                root = list.get(0);
                flag = true;
                break;
            }

        }


        return flag;
    }



    protected class Node<T> implements Comparable<Node> {
        T data;
        Integer weight;
        Node<T> leftNode;
        Node<T> rightNode;

        public T getData() {
            return data;
        }

        public Node<T> getLeftNode() {
            return leftNode;
        }

        public void setLeftNode(Node<T> leftNode) {
            this.leftNode = leftNode;
        }

        public Node<T> getRightNode() {
            return rightNode;
        }

        public void setRightNode(Node<T> rightNode) {
            this.rightNode = rightNode;
        }

        public  void preOrder(Node node, StringBuilder sb) {


            sb.append(node.toString() + ", ");

            if(node.leftNode != null) {

                preOrder(node.leftNode, sb);
            }

            if(node.rightNode != null) {
                preOrder(node.rightNode, sb);
            }

        }


        public  void inOrder(Node node, StringBuilder sb) {

            if(node.leftNode != null) {

                inOrder(node.leftNode, sb);
            }

            sb.append(node.toString() + ", ");


            if(node.rightNode != null) {
                inOrder(node.rightNode, sb);
            }

        }

        public void setData(T data) {
            this.data = data;

            //节点的权重硬性规定为数据data内部的权重
            try {
                Field field = data.getClass().getDeclaredField("weight");
                field.setAccessible(true);

                weight = (Integer) field.get(data);
            } catch (Exception e) {
                e.printStackTrace();
            }

        }

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

        // node排序必须要实现这个函数 大于实参则大于0 小于则小于0 等于则等于0
        @Override
        public int compareTo(Node node) {
            return this.weight - node.weight;
        }
    }


    public static void main(String[] args) {


        //1. 数据准备 - 为什么写那么麻烦，主要是写熟悉一些数组、链表之间的转换函数
        Student student1 = new Student(1, "lrc", 8);
        Student student2 = new Student(2, "qcj", 2);
        Student student3 = new Student(3, "ert", 10);
        Student student4 = new Student(4, "bfg", 5);
        Student student5 = new Student(5, "ytu", 25);
        Student[] stu = {student1,student2,student3,student4,student5};
        // 2  5 8 10 25
        // 7 8 10 25
        // 10 15 25
        // 25 25
        // 50

        //2. 构造最优二叉树
        OptimalBinaryTree<Student> tree = new OptimalBinaryTree(stu);

        //3. 前序遍历二叉树
        System.out.println(tree);


    }

}

HuffmanCode.java

package top.linruchang.algorithm.tree;

import java.util.*;

/**
 * @Classname HuffmanCode
 * @Description
 * @Date 2020/4/13 21:27
 * @Created by lrc
 */
public class HuffmanCode {

    // 根据data字符个数构建赫夫曼二叉树
    OptimalBinaryTree<MyCharacter> tree;

    //需要被赫夫曼编码的原字符串
    String data;

    //赫夫曼编码字符串data
    String encodedData;

    //压缩encodedData的数据
    byte[] encodedDataArray;

    //存储data字符串对应的每个字符个数记录
    HashMap<Character, MyCharacter> charMap;

    //根据tree获取对应字符的赫夫曼编码
    HashMap<Character, String> codeMap = new HashMap<>();


    HuffmanCode(String str) {

        //需要被赫夫曼编码的原字符串
        this.data = str;

        // 1. 计算字符串各个字符出现的次数
        initCharMap(str);
        System.out.println("每个字符出现的次数：" + charMap);

        // 2. 构造最优二叉树
        MyCharacter[] myCharacters = new MyCharacter[charMap.size()];
        charMap.values().toArray(myCharacters);
        tree = new OptimalBinaryTree<>(myCharacters);
        System.out.println("前序遍历赫夫曼树：" + tree);


        //3. 根据tree获取对应字符的赫夫曼编码
        initHuffmanCode(tree.getRoot(), "", new StringBuilder());
        System.out.println("编码转换规则" + codeMap);


        //4. 根据codeMap字符编码规则将data字符串转成二进制编码
        EncodingData();
        System.out.println("原字符串：" + data);
        System.out.println("赫夫曼编码后的字符串：" + encodedData);


        //5. 压缩encodedData
        zipCode();

    }


    public HashMap<Character, String> getCodeMap() {
        return codeMap;
    }

    /**
     *  解码
     * @param binaryMessg 字节数组
     * @param codeMap  赫夫曼编码规则
     * @return  返回原字符串
     */
    public static String decode(byte[] binaryMessg, Map< Character, String> codeMap) {

        String encodedDataByBytes = getEncodedDataByBytes(binaryMessg, codeMap);

        return decode(encodedDataByBytes, codeMap);

    }


    /**
     *
     * @param binaryMessg 二进制字符串
     * @param codeMap  赫夫曼编码规则
     * @return 返回原字符串
     */
    public static String decode(String binaryMessg, Map< Character, String> codeMap) {

        StringBuilder textContent = new StringBuilder();

        Set<Map.Entry<Character, String>> entries = codeMap.entrySet();

        Integer startIndex = 0;

        while(true) {
            String code;
            Integer tempEndIndex;
            for(Map.Entry<Character, String> map: entries) {

                code = map.getValue();
                tempEndIndex = startIndex + code.length();
                if(tempEndIndex > binaryMessg.length()) {
                    continue;
                }

                String substr = binaryMessg.substring(startIndex, tempEndIndex);


                if(code.equals(substr)) {
                    textContent.append(map.getKey());
                    startIndex = tempEndIndex;
                    break;
                }
            }

            if(startIndex >= binaryMessg.length()) {
                break;
            }

        }
        return textContent.toString();
    }

    /**
     *
     * @param bytes  字节数组 - 存储了赫夫曼编码的信息
     * @param codeMap  匹配规则
     * @return  返回赫夫曼编码的二进制信息 - 根据这段信息进行解码
     */
    public static String getEncodedDataByBytes(byte[] bytes, Map< Character, String> codeMap) {

        StringBuilder sb = new StringBuilder();

        int j = 0;
        for(byte b : bytes) {

            String binStr = Integer.toBinaryString(b);

            if(binStr.length() <= 8) {

                if(j == bytes.length -1) {
                    sb = adjustString(sb, new StringBuilder(binStr), codeMap);
                    break;
                }

                for(int i = 0; i<8-binStr.length(); i++) {
                    sb.append("0");
                }
                sb.append(binStr);
            }
            if(binStr.length() > 8) {

                sb.append(binStr.substring(binStr.length()-8));
            }
            j++;
        }
        return sb.toString();

    }


    /**
     * 这段代码别看了，实在是太冗余，写完我都不想在看它，懒得重构
     * 修改最后一段二进制与前面一段二进制 - 因为Integer.toBinaryString得到的补码会忽略到前面的0，故需要补全
     * @param prefixSb
     * @param suffixSb
     * @param codeMap
     * @return
     */
    public static StringBuilder adjustString(StringBuilder prefixSb, StringBuilder suffixSb, Map< Character, String> codeMap) {

        //1. 找到前半段没有匹配的二进制字符
        Integer startIndex = 0;
        Integer endIndex = 0;

        String prefixStr = prefixSb.toString();
        String suffixStr = suffixSb.toString();

        Collection<String> codes = codeMap.values();

        Integer count = 0;
        while(true) {
            ++count;
            //遍历查询前缀字符对应赫夫曼编码

            //说明持续验证最后一段都不能找到对应的赫夫曼编码
            if(count == 2) {
                break;
            }

            for(String code : codes) {
                Integer curEndIndex = startIndex + code.length();

                //截图的结束索引大于被截取字段本身 - 则忽略该次查询
                if(curEndIndex > prefixSb.length()) {
                    continue;
                }

                String substr = prefixStr.substring(startIndex, curEndIndex);

                if(code.equals(code)) {
                    startIndex = curEndIndex;
                    endIndex = curEndIndex;
                    count = 0;
                    break;
                }
            }

            //前半段都符合编码情况
            if(startIndex >= prefixSb.length()) {
                break;
            }

        }

        // 2.找到赫夫曼编码符合修复条件的几个编码
        String waitPrefixStr = null;
        List<String> waitPrefixStrs = new ArrayList<String>();


        if(startIndex != prefixStr.length()) {
            waitPrefixStr = prefixStr.substring(startIndex);
            System.out.println("waitPrefix：" + waitPrefixStr);


            //查找修复前缀字段等待字段
            for(String code : codes) {

                //只有短过赫夫曼编码的才是需要被修复，否则不用修复
                if(code.length() > waitPrefixStr.length()) {
                    boolean isMatch = code.substring(0,waitPrefixStr.length()).matches(waitPrefixStr);

                    if(isMatch) {

                        //waitPrefixStr只有末尾等于有0才用修复，否则不用修复
                        if(code.charAt(waitPrefixStr.length()) == '0') {
                            waitPrefixStrs.add(code);
                        }
                    }
                }
            }

        }



        //3. 真正的修复前半段 - 利用waitPrefixStrs进行依依比对
        if(waitPrefixStrs.size() > 0) {

            String copyWaitPrefixStr = new String(waitPrefixStr);
            for(String repairTarget : waitPrefixStrs) {

                for(int index = waitPrefixStr.length(); index < repairTarget.length(); index++) {

                    if(repairTarget.charAt(index) == '0') {
                        copyWaitPrefixStr += "0";
                    }else {
                        break;
                    }
                }

                String tempSuffixStr = copyWaitPrefixStr + suffixStr;

                Integer sufixStartIndex = 0;

                Integer suffixCount = 0;

                //验证当前的copyWaitPrefixStr是否是需要的
                boolean isValid = false;
                while(true) {
                    ++suffixCount;

                    if(suffixCount == 2) {
                        break;
                    }

                    for(String code : codes) {

                        Integer curSuffixEndIndex = sufixStartIndex + code.length();

                        if(curSuffixEndIndex > tempSuffixStr.length()) {
                            continue;
                        }

                        if(tempSuffixStr.substring(sufixStartIndex, curSuffixEndIndex).equals(code)) {
                            sufixStartIndex = curSuffixEndIndex;
                            suffixCount = 0;
                            break;
                        }

                    }

                    if(sufixStartIndex == tempSuffixStr.length()) {
                        isValid = true;
                        break;
                    }

                }

                if(isValid) {

                    for(int index = waitPrefixStr.length(); index < repairTarget.length(); index++) {

                        if(repairTarget.charAt(index) == '0') {
                            prefixSb.append("0");
                        }else {
                            break;
                        }
                    }
                    break;

                }

            }

        }

        return prefixSb.append(suffixSb);
    }

    public String getEncodedData() {
        return encodedData;
    }

    private void zipCode() {
        byte[] bytes;

        //1.获取数组长度
        Integer length = encodedData.length();
        if (length % 8 == 0) {
            bytes = new byte[length / 8];
        } else {
            bytes = new byte[length / 8 + 1];
        }


        //2.每8位截取一段字符（补码），将其转成10进制
        Integer startIndex = 0;
        Integer endIndex = 8;
        Integer byteIndex = 0;
        while (startIndex < length - 1) {

            String binaryNum = encodedData.substring(startIndex, endIndex);
            System.out.println(binaryNum);
            Integer num = Integer.valueOf(binaryNum, 2);
            bytes[byteIndex++] = num.byteValue();
            startIndex += 8;
            endIndex += 8;

            if (endIndex > length) {
                endIndex = length;
            }
        }

        //3.返回字节数组
        encodedDataArray = bytes;
    }

    public byte[] getEncodedDataBytes() {
        return encodedDataArray;
    }

    public void EncodingData() {

        char[] chars = new char[data.length()];
        data.getChars(0, data.length(), chars, 0);

        StringBuilder sb = new StringBuilder();
        for (char curChar : chars) {
            String code = codeMap.get(curChar);
            sb.append(code);
        }
        encodedData = sb.toString();

    }

    /**
     * 根据赫夫曼树 - 获取字符赫夫曼编码
     *
     * @param node   当前节点
     * @param signLR 标记是左节点还是右节点  0：左节点  1：右节点
     * @param sb     存储到达路径  --根据上述signLR存储 -- 字符赫夫曼编码
     */
    private void initHuffmanCode(OptimalBinaryTree.Node node, String signLR, StringBuilder sb) {

        StringBuilder sb2 = new StringBuilder(sb);
        sb2.append(signLR);

        if (node != null) {

            if (node.data == null) {

                initHuffmanCode(node.leftNode, "0", sb2);

                initHuffmanCode(node.rightNode, "1", sb2);

            } else {
                Character curCharacter = ((MyCharacter) node.getData()).getCharacter();
                codeMap.put(curCharacter, sb2.toString());
            }

        }

    }

    //计算原字符串各个字符出现的次数
    private void initCharMap(String str) {
        char[] chars = new char[str.length()];
        str.getChars(0, str.length(), chars, 0);

        charMap = new HashMap<>();
        for (char curChar : chars) {

            boolean hasKey = charMap.containsKey(curChar);

            MyCharacter curCharacter;
            if (hasKey) {
                curCharacter = charMap.get(curChar);
                Integer count = curCharacter.getCount();
                curCharacter.setCount(++count);
            } else {

                curCharacter = new MyCharacter();
                curCharacter.setCharacter(curChar);
                curCharacter.setCount(1);
                charMap.put(curChar, curCharacter);
            }

        }
    }

    //内部类 - 用来存储原字符串对应的字符以及出现次数、以及节点权重
    private class MyCharacter implements Comparable<MyCharacter> {

        Character character;
        Integer asciiValue;
        Integer count;
        Integer weight;

        public Character getCharacter() {
            return character;
        }

        public void setCharacter(Character character) {
            this.character = character;
            this.asciiValue = (int) character.charValue();
        }

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
            this.weight = count;
        }

        @Override
        public String toString() {
            return "MyCharacter{" +
                    "character=" + character +
                    ", asciiValue=" + asciiValue +
                    ", count=" + count +
                    '}';
        }

        @Override
        public int compareTo(MyCharacter orderCharacter) {
            return this.count - orderCharacter.count;
        }
    }


    public static void main(String[] args) {


//        String str = "abcfdef tratr egcs";
        String str = "I love you";

        HuffmanCode code = new HuffmanCode(str);

        System.out.println("赫夫曼编码后二进制转成字节数组：" + Arrays.toString(code.getEncodedDataBytes()));

        //通过字节数组进行节码
        byte[] bytes = code.getEncodedDataBytes();

        //将字节数组转成二进制字符串 - 通过二进制字符串转成原字符串明文
        String encodeStr = HuffmanCode.getEncodedDataByBytes(bytes, code.getCodeMap());
        System.out.println("赫夫曼编码二进制字符串：" + encodeStr);
        System.out.println(code.decode(encodeStr, code.getCodeMap()));
        System.out.println(code.decode(bytes, code.getCodeMap()));


        Integer length1 = str.length() * 8;
        Integer length2 = code.getEncodedData().length();
        double redPer = (length1 - length2) / (double) length1;
        System.out.printf("固定长度ascii编码长度length1：%d，赫夫曼编码后长度length2：%d，所以减少率为：%f\n", length1, length2, redPer);

    }

}

小半

0 0

生成海报 微信扫码分享