当给出下列字母字符的频率时，写下Huffman Coding 以及考虑这个频率的霍夫曼码的查找过程。

Question

当给出下列字母字符的频率时，Huffman Coding 以及考虑这个频率的霍夫曼码的查找过程。

Huffman Coding：
英文字母频率 （％）Huffman Coding

A 20

E 40

O 10

R 15

P 9

K 3

Q 2

Z 1

Answer 1

字母就是一个字符，对应的频率就是它的权重。哈夫曼编码思想就是构建n棵只有根节点的二叉树，组成森林，根节点的值为n个字母与权值。
代码测试结果：希望能采纳答案

/**
 * @author Charzous
 * @date 2022-04-14
 * 哈夫曼树编码
 */
public class HuffmanCode {
    final int n = 8;
    int i1, i2;

    static class Node {
        String code = "";
        char data = ' ';
        int weight = 0;
        int parent = 0, lChild = 0, rChild = 0;
        int idx = -1;
        int LR = 0;
    }

    public void select(Node[] huffTree) {
        /**
         * @param huffTree
         * @author Charzous
         * @date 2022-04-14
         * 对每个字符按照权重进行排序，标记，为创建树做准备
         */
        int count = 0;
        int i, j;
        int len = 2 * n - 1;
        Node[] reserve = new Node[len];
        for (i = 0; i < len; i++) {
            huffTree[i].idx = i;
            reserve[i] = huffTree[i];
        }

        for (i = 0; i < len; i++) {
            for (j = 0; j < len - i; j++) {
                if (huffTree[j].weight > huffTree[j + 1].weight) {
                    Node temp = huffTree[j + 1];
                    huffTree[j + 1] = huffTree[j];
                    huffTree[j] = temp;
                }
            }
        }

        for (i = 0; i < len; i++) {
            if (count == 0 && huffTree[i].parent == -1) {
                i1 = huffTree[i].idx;
                count = 1;
                continue;
            }
            if (count == 1 && huffTree[i].parent == -1) {
                i2 = huffTree[i].idx;
                break;
            }
        }

        for (i = 0; i < len; i++) {
            huffTree[i] = reserve[i];
        }
    }

    public void createHuffmanTree(Node[] huffTree, int[] weight, char[] ch) {
        /**
         * @param huffTree
         * @param weight
         * @param ch
         * @author Charzous
         * @date 2022-04-14
         * 哈夫曼编码思想：构建n棵只有根节点的二叉树，组成森林
         */
        int i, j, k;
        int len = 2 * n - 1;
        for (i = 0; i < len; i++) {
            huffTree[i].parent = -1;
            huffTree[i].lChild = huffTree[i].rChild = -1;
            huffTree[i].weight = Integer.MAX_VALUE;
            huffTree[i].data = '\0';
        }

        for (i = 0; i < n; i++) {
            huffTree[i].weight = weight[i];
            huffTree[i].data = ch[i];
        }

        for (k = n; k < len; k++) {
            select(huffTree);
            huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;

            huffTree[i1].parent = huffTree[i2].parent = k;        //设置父索引是k
            huffTree[k].lChild = i1;
            huffTree[k].rChild = i2;    //设置左子索引是i1，右子索引是i2
            huffTree[i1].LR = 0;
            huffTree[i2].LR = 1;        //用来唯一的表示是左孩子还是右孩子
            System.out.println("第" + (k - n + 1) + "次结点合并权值最小的两个根节点下标：");
            System.out.println(i1 + "和" + i2);
            ;
        }
    }


    public void huffTreeStruct(Node[] huffTree) {
        /**
         * @param huffTree
         * @return void
         * @author Charzous
         * @date 2022-04-14
         * 打印哈夫曼树结构
         */
        System.out.println("\n哈夫曼树结构：");
        System.out.println("下标\t权重\t父索引\t左子索引\t右子索引\t字符");
        for (int i = 0; i < 2 * n - 1; i++) {
            System.out.println(i + "\t" + huffTree[i].weight + "\t" + huffTree[i].parent + "\t" + huffTree[i].lChild + "\t" + huffTree[i].rChild + "\t" + huffTree[i].data);
        }
        System.out.println();
    }

    //根据权重来实现哈夫曼编码
    public void EnHuffmanCode(Node[] huffTree) {
        /**
         * @param huffTree
         * @return void
         * @author Charzous
         * @date 2022-04-14
         * 为节点哈夫曼编码
         */
        for (int i = 0; i < n; i++) {    //有n个叶子结点，就要进行n次编码，左子树编码为0，右子树编码为1的规则
            int j = i;        //利用j来存储i以便于后面不至于改变i的值
            while (huffTree[i].parent != -1) {        //循环至根节点停止
                if (huffTree[i].LR == 0) {    //如果该叶子结点的索引等于他父节点的左孩子的索引，也就是判断该结点是他父节点的左孩子，就给编码前面加上"0"
                    huffTree[j].code = "0" + huffTree[j].code;        //如果是左孩子就在前面添加上"0"字符
                    i = huffTree[i].parent;        //将i用父节点的下标代替
                }
                if (huffTree[i].LR == 1) {    //如果该叶子结点的索引等于他父节点的右孩子的索引，也就是判断该结点是他父节点的右孩子，就给编码前面加上"1"
                    huffTree[j].code = "1" + huffTree[j].code;
                    i = huffTree[i].parent;        //将i用父节点的下标代替
                }
            }
            i = j;    //将保存了i的j赋值给i
        }
    }

    public void printCode(Node[] huffTree) {
        /**
         * @param huffTree
         * @return void
         * @author Charzous
         * @date 2022-04-14
         * 打印哈夫曼编码
         */
        System.out.println("对字符的哈夫曼编码：");
        for (int i = 0; i < n; i++) {
            System.out.println(huffTree[i].data + "的编码是：" + huffTree[i].code);
        }
    }
//    测试
    public static void main(String[] args) {
        int n = 8;
        char[] ch = {'A', 'E', 'R', 'O', 'P', 'K', 'Q', 'Z'};
        int[] weight = { 20, 40, 15, 10, 9, 3, 2, 1};
        HuffmanCode huffmanCode = new HuffmanCode();
        Node[] huffTree = new Node[2 * n];
        for (int i = 0; i < 2 * n; i++) {
            huffTree[i] = new Node();
        }
        huffmanCode.createHuffmanTree(huffTree, weight, ch);
        huffmanCode.EnHuffmanCode(huffTree);
        huffmanCode.huffTreeStruct(huffTree);
        huffmanCode.printCode(huffTree);

    }
}

代码测试正确， 可以直接用，希望能采纳答案