Java（11）

学习来源：日撸 Java 三百行（21-30天，树与二叉树）

第 28 天: Huffman 编码 (节点定义与文件读取)

输入：输入表示文本文件的字符串paraFilename
输出：构造对象tempHuffman并输出文本文件的内容inputText
优化目标：无

ps：每个节点的内容包括：字符 (仅对叶节点有效)、权重 (表示该字符的个数)、指向子节点和父节点的引用。

package my_java;import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.stream.Collectors;/*** @Description: Huffman tree* @author: Xin-Yu Li* @date: 2022年4月19日*/
public class Huffman {class HuffmanNode {char character;int weight;HuffmanNode leftChild;HuffmanNode rightChild;HuffmanNode parent;public HuffmanNode(char paraCharacter, int paraWeight, HuffmanNode paraLeftChild,HuffmanNode paraRightChild, HuffmanNode paraParent) {character = paraCharacter;weight = paraWeight;leftChild = paraLeftChild;rightChild = paraRightChild;parent = paraParent;}// Of HuffmanNodepublic String toString() {String resultString = "(" + character + ", " + weight + ")";return resultString;}// Of toString}// Of class HuffmanNodepublic static final int NUM_CHARS = 256;String inputText;int alphabetLength;char[] alphabet;int[] charCounts;int[] charMapping;String[] huffmanCodes;HuffmanNode[] nodes;/*** @Description: The first constructor.* @param paraFilename The text filename.*/public Huffman(String paraFilename) {charMapping = new int[NUM_CHARS];readText(paraFilename);}// Of the first constructor/*** @Description: Read text.* @param paraFilename The text filename.*/public void readText(String paraFilename) {try {inputText = Files.newBufferedReader(Paths.get(paraFilename), StandardCharsets.UTF_8).lines().collect(Collectors.joining("\n"));} catch (Exception ee) {System.out.println(ee);System.exit(0);} // Of trySystem.out.println("The text is:\r\n" + inputText);}// Of readTextpublic static void main(String args[]) {Huffman tempHuffman = new Huffman("C:/Users/94296/Desktop/huffman.txt");}// Of main}// Of class Huffman

运行截图：
在这里插入图片描述

第 29 天: Huffman 编码 (建树)

建树就是一个自底向上，贪心选择的过程。确定子节点、父节点的代码是核心。

输入：输入文本文件的内容inputText来构建哈夫曼树
输出：输出inputText中出现过的字符、字符的权重、建树选结点的过程以及根节点。
优化目标：无

	/*** @Description: Construct the alphabet.*/public void constructAlphabet() {Arrays.fill(charMapping, -1);//这种初始化工作非常重要int[] tempCharCounts = new int[NUM_CHARS];int tempCharIndex;char tempChar;for (int i = 0; i < inputText.length(); i++) {tempChar = inputText.charAt(i);tempCharIndex = (int) tempChar;//将 char强制转换为 int, 即其在 ASCII字符集中的位置System.out.print("" + tempCharIndex + " ");tempCharCounts[tempCharIndex]++;} // Of for ialphabetLength = 0;for (int i = 0; i < 255; i++) {if (tempCharCounts[i] > 0) {alphabetLength++;} // Of if} // Of for i//Compress to the alphabetalphabet = new char[alphabetLength];charCounts = new int[2 * alphabetLength - 1];int tempCounter = 0;for (int i = 0; i < NUM_CHARS; i++) {if (tempCharCounts[i] > 0) {alphabet[tempCounter] = (char) i;//tempCounter位置存储的字符charCounts[tempCounter] = tempCharCounts[i];//该字符的个数charMapping[i] = tempCounter;//i表示在ASCII字符集中的位置tempCounter++;} // Of if} // Of for iSystem.out.println("The alphabet is: " + Arrays.toString(alphabet));System.out.println("Their counts are: " + Arrays.toString(charCounts));System.out.println("The char mappings are: " + Arrays.toString(charMapping));}// Of constructAlphabet/** * @Description: Construct the tree.*/public void constructTree() {nodes = new HuffmanNode[alphabetLength * 2 - 1];boolean[] tempProcessed = new boolean[alphabetLength * 2 - 1];//建立叶子结点for (int i = 0; i < alphabetLength; i++) {nodes[i] = new HuffmanNode(alphabet[i], charCounts[i], null, null, null);} // Of for iint tempLeft, tempRight, tempMinimal;for (int i = alphabetLength; i < 2 * alphabetLength - 1; i++) {//选择权值最小的作为左孩子tempLeft = -1;tempMinimal = Integer.MAX_VALUE;for (int j = 0; j < i; j++) {if (tempProcessed[j]) {continue;} // Of ifif (tempMinimal > charCounts[j]) {tempMinimal = charCounts[j];tempLeft = j;} // Of if} // Of for jtempProcessed[tempLeft] = true;//选择权值第二小的作为右孩子tempRight = -1;tempMinimal = Integer.MAX_VALUE;for (int j = 0; j < i; j++) {if (tempProcessed[j]) {continue;} // Of ifif (tempMinimal > charCounts[j]) {tempMinimal = charCounts[j];tempRight = j;} // Of if} // Of for jtempProcessed[tempRight] = true;System.out.println("Selecting " + tempLeft + " and " + tempRight);//建立链接两个孩子结点的新结点charCounts[i] = charCounts[tempLeft] + charCounts[tempRight];nodes[i] = new HuffmanNode('*', charCounts[i], nodes[tempLeft], nodes[tempRight], null);//孩子结点指向父节点nodes[tempLeft].parent = nodes[i];nodes[tempRight].parent = nodes[i];System.out.println("The children of " + i + " are " + tempLeft + " and " + tempRight);} // Of for i}// Of constructTree/*** @Description: Get the root of the binary tree.* @return The root.*/public HuffmanNode getRoot() {return nodes[nodes.length - 1];}// Of getRootpublic static void main(String args[]) {Huffman tempHuffman = new Huffman("C:/Users/94296/Desktop/huffman.txt");tempHuffman.constructAlphabet();tempHuffman.constructTree();HuffmanNode tempRoot = tempHuffman.getRoot();System.out.println("The root is: " + tempRoot);}// Of main

运行截图：
在这里插入图片描述

第 30 天: Huffman 编码 (编码与解码)

编码是从叶节点到根节点，解码就是反过来。

输入：输入文本文件的内容inputText来构建哈夫曼树以及输入待编码字符串“hello”
输出：输出哈夫曼树的先序遍历序列、每个字符的编码以及待编码字符串的编码和解码过程
优化目标：无

	/*** @Description: Pre-order visit.* @param paraNode The Root*/public void preOrderVisit(HuffmanNode paraNode) {System.out.print("(" + paraNode.character + ", " + paraNode.weight + ") ");if (paraNode.leftChild != null) {preOrderVisit(paraNode.leftChild);} // Of ifif (paraNode.rightChild != null) {preOrderVisit(paraNode.rightChild);} // Of if}// Of preOrderVisit/*** @Description: Generate codes for each character in the alphabet.* @param none*/public void generateCodes() {huffmanCodes = new String[alphabetLength];HuffmanNode tempNode;for (int i = 0; i < alphabetLength; i++) {tempNode = nodes[i];String tempCharCode = "";while (tempNode.parent != null) {if (tempNode == tempNode.parent.leftChild) {tempCharCode = "0" + tempCharCode;} else {tempCharCode = "1" + tempCharCode;} // Of iftempNode = tempNode.parent;} // Of whilehuffmanCodes[i] = tempCharCode;System.out.println("The code of " + alphabet[i] + " is " + tempCharCode);} // Of for i}// Of generateCodes/*** @Description: Encode the given string.* @param paraString The given string.*/public String coding(String paraString) {String resultCodeString = "";int tempIndex;for (int i = 0; i < paraString.length(); i++) {tempIndex = charMapping[(int) paraString.charAt(i)];resultCodeString += huffmanCodes[tempIndex];} // Of for ireturn resultCodeString;}// Of coding/*** @Description: Decode the given string.* @param paraString The given string.*/public String decoding(String paraString) {String resultCodeString = "";HuffmanNode tempNode = getRoot();for (int i = 0; i < paraString.length(); i++) {if (paraString.charAt(i) == '0') {tempNode = tempNode.leftChild;System.out.println(tempNode);} else {tempNode = tempNode.rightChild;System.out.println(tempNode);} // Of ifif (tempNode.leftChild == null) {System.out.println("Decode one:" + tempNode);resultCodeString += tempNode.character;tempNode = getRoot();} // Of if} // Of for ireturn resultCodeString;}// Of decodingpublic static void main(String args[]) {Huffman tempHuffman = new Huffman("C:/Users/94296/Desktop/huffman.txt");tempHuffman.constructAlphabet();tempHuffman.constructTree();HuffmanNode tempRoot = tempHuffman.getRoot();System.out.println("The root is: " + tempRoot);tempHuffman.preOrderVisit(tempHuffman.getRoot());tempHuffman.generateCodes();//前序遍历代码的作用仅仅是调拭String tempCoded = tempHuffman.coding("abcdb");System.out.println("Coded: " + tempCoded);String tempDecoded = tempHuffman.decoding(tempCoded);System.out.println("Decoded: " + tempDecoded);}// Of main