日撸代码300行（21-30天，树与二叉树）

日撸代码300行（21-30天，树与二叉树）

原文：日撸代码300行（21-30天，树与二叉树）_minfanphd的博客-CSDN博客

目录

• 日撸代码300行（21-30天，树与二叉树）
• • 21.二叉树的深度遍历的递归实现
  • 22.二叉树的存储
  • 23.使用具有通用性的队列
  • 24.二叉树的建立
  • 25.二叉树深度遍历的栈实现 (中序)
  • 26.二叉树深度遍历的栈实现 (前序和后序)
  • 27.Hanoi 塔问题
  • 28-30. Huffman

21.二叉树的深度遍历的递归实现

package day30.tree;/*** Day:21 二叉树** @author pzf*/
public class BinaryCharTree {// attributespublic char value;public BinaryCharTree leftChild, rightChild;// contractorpublic BinaryCharTree(char paraValue) {this.value = paraValue;this.leftChild = null;this.rightChild = null;}// Of contractor/*** 先序遍历*/public void preOrder() {System.out.print(value + " ");if (this.leftChild != null) {this.leftChild.preOrder();}// Of ifif (this.rightChild != null) {this.rightChild.preOrder();}// Of if}// Of preOrder/*** 中序遍历*/public void inOrder() {if (this.leftChild != null) {this.leftChild.inOrder();}// Of ifSystem.out.print(value + " ");if (this.rightChild != null) {this.rightChild.inOrder();}// Of if}// Of inOrder/*** 后序遍历*/public void postOrder() {if (this.leftChild != null) {this.leftChild.postOrder();}// Of ifif (this.rightChild != null) {this.rightChild.postOrder();}// Of ifSystem.out.print(value + " ");}// Of postOrder/*** 生成一个树** @return 一个树*/public static BinaryCharTree manualConstructTree() {// Step 1. Construct a tree with only one node.BinaryCharTree resultTree = new BinaryCharTree('a');// Step 2. Construct all nodes. The first node is the root.// BinaryCharTreeNode tempTreeA = resultTree.root;BinaryCharTree tempTreeB = new BinaryCharTree('b');BinaryCharTree tempTreeC = new BinaryCharTree('c');BinaryCharTree tempTreeD = new BinaryCharTree('d');BinaryCharTree tempTreeE = new BinaryCharTree('e');BinaryCharTree tempTreeF = new BinaryCharTree('f');BinaryCharTree tempTreeG = new BinaryCharTree('g');// Step 3. Link all nodes.resultTree.leftChild = tempTreeB;resultTree.rightChild = tempTreeC;tempTreeB.rightChild = tempTreeD;tempTreeC.leftChild = tempTreeE;tempTreeD.leftChild = tempTreeF;tempTreeD.rightChild = tempTreeG;return resultTree;}/*** 获取树深度** @return int 树深度*/public int getDepth() {if (this.leftChild == null && this.rightChild == null) {return 1;}// Of ifif (this.leftChild == null) {return this.rightChild.getDepth() + 1;}// Of ifif (this.rightChild == null) {return this.leftChild.getDepth() + 1;}// Of ifreturn 1 + Math.max(this.leftChild.getDepth(), this.rightChild.getDepth());}// Of getDepth/*** 获取节点数** @return int 节点总数*/public int getNum() {// leafif (this.leftChild == null && this.rightChild == null) {return 1;}// Of ifint leftCount = 0;if (this.leftChild != null) {leftCount =  this.leftChild.getNum();}// Of ifint rightCount = 0;if(this.rightChild != null){rightCount = this.rightChild.getNum();}// Of ifreturn leftCount + rightCount + 1;}// Of getNum/*** main** @param args*/public static void main(String[] args) {BinaryCharTree btree = manualConstructTree();btree.preOrder();System.out.println("\n");btree.inOrder();System.out.println("\n");btree.postOrder();System.out.println("\n");System.out.println(btree.getDepth());System.out.println(btree.getNum());}// Of main
}// Of class BinaryCharTree

生成树的方法直接摘抄原文闵老师的，创建的二叉树如下：

测试运行结果：

22.二叉树的存储

1.Object版循环队列

package day20;/*** Object版本队列*/
public class AnyQueue {public final int MAX_LENGTH = 10;int head,tail;Object[] data;public AnyQueue(){data = new Object[MAX_LENGTH];head = 0;tail = 0;}public boolean enqueue(Object paraObject){if((tail + 1) % MAX_LENGTH == head){System.out.println("Full");return false;}data[tail % MAX_LENGTH] = paraObject;tail = (tail + 1) % MAX_LENGTH;return true;}public Object dequeue(){if( head == tail ){System.out.println("Empty");return null;}Object res = data[head % MAX_LENGTH];head = (head + 1) % MAX_LENGTH;return res;}public String toString(){String resultString = "";if (head == tail) {return "empty";} // Of iffor (int i = head; i < tail; i++) {resultString += data[i % MAX_LENGTH] + ", ";} // Of for iresultString = resultString.substring(0,resultString.length()-2);return resultString;}}

2.储存

	char[] valuesArray;int [] indicesArray;/*** 用2个数组储存二叉树* eg. [a, b, c, d, e, f, g]*     [0, 1, 2, 4, 5, 9, 10]*/public void toDataArrays(){int tempLength = this.getNum();valuesArray = new char[tempLength];indicesArray = new int[tempLength];int i=0;AnyQueue tempQueue = new AnyQueue();CircleQueue tempIntQueue = new CircleQueue();// roottempQueue.enqueue(this);tempIntQueue.enqueue(0);// tempTree : rootBinaryCharTree tempTree = (BinaryCharTree) tempQueue.dequeue(); // Object -> BinaryCharTreeint tempIndex = tempIntQueue.dequeue(); // tempIndex = 0while(tempTree != null){valuesArray[i] = tempTree.value;indicesArray[i] = tempIndex;i++;// levelOrderif(tempTree.leftChild != null){tempQueue.enqueue(tempTree.leftChild);tempIntQueue.enqueue(2 * tempIndex + 1);}// Of ifif(tempTree.rightChild != null){tempQueue.enqueue((tempTree.rightChild));tempIntQueue.enqueue(2 * tempIndex + 2);}// Of iftempTree = (BinaryCharTree) tempQueue.dequeue();tempIndex = tempIntQueue.dequeue();}// Of while}// Of toDataArrays/*** main*/public static void main(String[] args) {BinaryCharTree btree = manualConstructTree();btree.toDataArrays();System.out.println(Arrays.toString(btree.valuesArray));System.out.println(Arrays.toString(btree.indicesArray));}// Of main

此方法及2个全局变量在day21的类中。

小结：
1.第一遍看闵老师的代码都没想通，最后醒悟是因为想起来了左孩子的下标是（节点下标 * 2 - 1）
2.在Day20的总结里面，最后那个问题是用通配符解决的，为了保持一致，直接抄了那个Object版的队列（懒）.
然后用通配符的那个版本试了试，没有问题，代码如下：

	char[] valuesArray;int [] indicesArray;/*** 用2个数组储存二叉树* eg. [a, b, c, d, e, f, g]*     [0, 1, 2, 4, 5, 9, 10]*/public void toDataArrays(){int tempLength = this.getNum();valuesArray = new char[tempLength];indicesArray = new int[tempLength];int i=0;CircleAnyQueue<TreeVersionTest> testQueue = new CircleAnyQueue<>();CircleAnyQueue<Integer> testIntQueue = new CircleAnyQueue<>();// roottestQueue.enqueue(this);testIntQueue.enqueue(0);// tempTree : rootTreeVersionTest tempTree = testQueue.dequeue();// Integer!!Integer tempIndex = testIntQueue.dequeue(); // tempIndex = 0while(tempTree != null){valuesArray[i] = tempTree.value;indicesArray[i] = tempIndex;i++;// levelOrderif(tempTree.leftChild != null){testQueue.enqueue(tempTree.leftChild);testIntQueue.enqueue(2 * tempIndex + 1);}// Of ifif(tempTree.rightChild != null){testQueue.enqueue(tempTree.rightChild);testIntQueue.enqueue(2 * tempIndex + 2);}// Of iftempTree = testQueue.dequeue();tempIndex = testIntQueue.dequeue();}// Of while}// Of toDataArrays

23.使用具有通用性的队列

和之前的代码一样，通过2种办法实现了通用性的队列。
1.使用Object类，所有类都是Object类的子类
2.泛型，通配符

今天没有什么代码，比较一下这两种方法：
1.通配符用于数组属性时，在构造方法里初始化会遇到问题。我的解决办法是把数组换成ArrayList.

public class CompareObject<T> {T[] name;ArrayList<T> title;Object[] voice;public CompareObject(){this.name =  new T[2]; // 报错 不可以用T创建数组this.title = new ArrayList<>();this.voice = new Object[5];}
public static void main(String[] args) {CompareObject<Integer> a = new CompareObject<>();}
}

2.使用Object类，需要转型，通配符不用。

	public Object getO() {return voice[0];}public T getT(){return this.title.get(0);}public static void main(String[] args) {CompareObject<Integer> a = new CompareObject<>();a.voice[0] = 1;int b = (int) a.getO();a.voice[0] = "String";String c = (String) a.getO();Integer d = a.getT();}

24.二叉树的建立

    /*** 构造方法** @param paraDataArray 装value的数组* @param paraIndicesArray 装下标的数组*/public BinaryCharTree(char[] paraDataArray, int[] paraIndicesArray){// 1.储存节点int tempNumNodes = paraDataArray.length;BinaryCharTree[] tempAllNodes = new BinaryCharTree[tempNumNodes ];for (int i = 0; i < tempNumNodes ; i++) {// 用value构造，tempAllNodes[]里放了所有节点tempAllNodes[i] = new BinaryCharTree(paraDataArray[i]);}// Of for// 2.连接节点for (int i = 1; i < tempNumNodes; i++) {// j是用来找父节点的for (int j = 0; j < i; j++) {// 谁的leftchild 是 iif(paraIndicesArray[j] * 2 + 1 == paraIndicesArray[i]){tempAllNodes[j].leftChild = tempAllNodes[i];break;}else if(paraIndicesArray[j] * 2 + 2 == paraIndicesArray[i]){tempAllNodes[j].rightChild = tempAllNodes[i];break;}// Of if}// Of for j}// Of for ivalue = tempAllNodes[0].value;leftChild = tempAllNodes[0].leftChild;rightChild = tempAllNodes[0].rightChild;}// Of contractor

这是一个构造方法，这个2层的for循环，是第一层从第二个节点开始，用第二层其之前遍历，看tempAllNodes[j]这个节点是tempAllNodes[i]的左还是右孩子，属于找父亲的思路。
我写的时候想的是第一层循环遍历节点，第二层循环从i+1开始，找孩子。一开始模仿闵老师代码犯了个错，在找到左孩子后就加了break，测试的时候发现只有左子树。修改后如下：

for (int i = 0; i < tempNumNodes; i++) {for (int j = i+1; j < tempNumNodes; j++) {if(paraIndicesArray[i] * 2 + 1 == paraIndicesArray[j]){tempAllNodes[i].leftChild = tempAllNodes[j];}else if(paraIndicesArray[i] * 2 + 2 == paraIndicesArray[j]){tempAllNodes[i].rightChild = tempAllNodes[j];break;}// Of if}// Of for j}// Of for i

属于找孩子的思路。

25.二叉树深度遍历的栈实现 (中序)

1.Object 通用栈

package day30.stack;/***  Object 通用栈** @author pzf*/
public class ObjectStack {// 变量public static final int MAX_DEPTH = 10;int depth;Object[] data;// 构造方法public ObjectStack() {depth = 0;data = new Object[MAX_DEPTH];}// Of the first constructor// toString 重写public String toString() {String resultString = "";for (int i = 0; i < depth; i++) {resultString += data[i];} // Of for ireturn resultString;}// Of toString/*** push 入栈** @param paraObject 入栈元素* @return true of false.*/public boolean push(Object paraObject) {if (depth == MAX_DEPTH) {System.out.println("Stack full.");return false;} // Of ifdata[depth] = paraObject;depth++;return true;}// Of push/*** 出栈** @return 出栈元素*/public Object pop() {if (depth == 0) {System.out.println("Nothing to pop.");return '\0';} // of ifObject resultObject = data[depth - 1];depth--;return resultObject;}// Of pop/*** 判空** @return true or false.*/public boolean isEmpty(){return depth == 0;}
}

2. 非递归中序遍历

	/*** 非递归中序遍历*/public void inOrderWithStack() {BinaryCharTree tempTree = this;ObjectStack tempStack = new ObjectStack();while (tempTree != null || !tempStack.isEmpty()) {if(tempTree != null){tempStack.push(tempTree);tempTree = tempTree.leftChild;}else{tempTree = (BinaryCharTree) tempStack.pop();System.out.print(tempTree.value + " "); // visittempTree = tempTree.rightChild;}// Of if}// Of while}// Of inOrderWithStack

26.二叉树深度遍历的栈实现 (前序和后序)

/*** 非递归前序遍历*/public void preOrderWithStack() {BinaryCharTree tempTree = this;ObjectStack tempStack = new ObjectStack();while (tempTree != null || !tempStack.isEmpty()) {if(tempTree != null){tempStack.push(tempTree);System.out.print(tempTree.value + " "); // visittempTree = tempTree.leftChild;}else{tempTree = (BinaryCharTree) tempStack.pop();tempTree = tempTree.rightChild;}// Of if}// Of whileSystem.out.println("\n");}// Of inOrderWithStack/*** 后序遍历，非递归*/public void postOrderWithStack(){BinaryCharTree tempTree = this;ObjectStack tempStack = new ObjectStack();ObjectStack tempValueStack = new ObjectStack();//1.中左右 -> 中右左while(tempTree != null || !tempStack.isEmpty()){if (tempTree != null){// 2. 入栈tempStack.push(tempTree);tempValueStack.push(tempTree.value);tempTree = tempTree.rightChild;}else{tempTree = (BinaryCharTree) tempStack.pop();tempTree = tempTree.leftChild;}// Of if}// Of while// 3.输出栈 倒序 中右左->左右中while (!tempValueStack.isEmpty()){System.out.print(""+ tempValueStack.pop() +" ");}// Of whileSystem.out.println("\n");}// Of postOrderWithStack

27.Hanoi 塔问题

Hanoi塔的问题很像那个楼梯题：一次只能上一层或者两层楼梯，问n层楼梯一共有多少种走法。就是n-1层的走法加上n-2层的走法。
Hanoi塔也一样，举个例子，1个碟只要1步，2个碟要3步（最大的碟移动一次，小的2次），3个碟可以把上面2个碟子看作一个整体（小），也就是2次整体+1，2个碟的移动是三步，也就是$2\ast (2+1)+1=7$；同理， 4个碟就把上面3个看成一个整体，步数是$2\ast 7+1=15$。
设n个碟的步数为$S(n)$，$S(n)=S(n-1)\ast 2+1,S(1)=1$

现在来分析一下输出每一步的思路，从左至右设底座为$a,b,c,$从2个碟的例子出发，分为三步
1.$a\to b$
2.$a\to c$
3.$b\to c$

再看3个碟的情况，把上面2个看做整体，就和2个碟的情况一样，整体的移动也是一次2个碟的移动，不过是把$c$当作$b$，所以总移动次数是 3+1+3=7

综上，可以把n个碟的情况分成三步：
1.除最大的碟以外（共n-1个）移动到$b$；
2.最大的碟移动到目标区域$c$；
3.剩下的n-1个碟移动到$c$.

所以，递归代码如下：

package day30.tree;/*** Hanoi** @author pzf*/
public class Hanoi {/**** @param a 起始点* @param b 中转点* @param c 目标点* @param n 数量*/public static void hanoi(char a, char b, char c,int n) {// 不接受0和负数个，且不接受太大的n,因为O(n^2)，递归太多if(n<=0 || n>20){System.out.println("Invalid input");return;}// 1个碟的情况，直接a->cif (n == 1) {System.out.println(a + "->" + c);return;} // Of if// 第一步. 把上面n-1个当作整体，移动到bhanoi(a, c, b, n - 1);// 第二步. 把最大的从a移动到c//hanoi(a,b,c,1) -> (n==1) -> print( a->c )System.out.println(a + "->" + c);// 第三步. 把第一步移动到b的n-1个移动到chanoi(b, a, c, n - 1);}// Of hanoipublic static void main(String[] args) {hanoi('a', 'b', 'c', 4);}// Of main}

28-30. Huffman

package day30.tree;import java.io.IOException;
import java.nio.charset.StandardCharsets;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.Arrays;
import java.util.stream.Collectors;/*** Day27-30 Huffman** @author pzf*/
public class Huffman {/*** Huffman节点类*/class HuffmanNode {// 变量char character; // 节点字符int weight;     // 权值HuffmanNode leftChild; // 左孩子HuffmanNode rightChild;// 右孩子HuffmanNode parent;    // 父节点/*** 构造方法** @param character  字符* @param weight     权* @param leftChild  左孩子* @param rightChild 右孩子* @param parent     父节点*/public HuffmanNode(char character, int weight, HuffmanNode leftChild, HuffmanNode rightChild,HuffmanNode parent) {this.character = character;this.weight = weight;this.leftChild = leftChild;this.rightChild = rightChild;this.parent = parent;}// Of contractor/*** 重写toString** @return 字符串*/public String toString() {String resultString = "(" + character + ", " + weight + ")";return resultString;}// Of toString}// Of class HuffmanNode// 常量 ASCII 256字符 128+128public static final int NUM_CHARS = 256;// 变量String inputText; // 文本内容int alphabetLength; // 字符表长度char[] alphabet; // 字符表int[] charCounts; // 计数表int[] charMapping; // 索引表String[] huffmanCodes;// 储存霍夫曼编码HuffmanNode[] nodes;// 储存霍夫曼树节点/*** 构造方法** @param paraFilename 文件地址*/public Huffman(String paraFilename) {charMapping = new int[NUM_CHARS];readText(paraFilename);}// Of contractor/*** 读取文件 ，并输出内容** @param paraFilename 文件地址*/public void readText(String paraFilename) {try {inputText =Files.newBufferedReader(Paths.get(paraFilename), StandardCharsets.UTF_8).lines().collect(Collectors.joining("\n"));} catch (IOException e) {e.printStackTrace();}// Of trySystem.out.println("The text is:\r\n" + inputText);}// Of readText/*** 构建字符表*/public void constructAlphabet() {// 初始化Arrays.fill(charMapping, -1);int[] tempCharCounts = new int[NUM_CHARS];int tempCharIndex;char tempChar;// 1.遍历文档，记录每个字符的次数for (int i = 0; i < inputText.length(); i++) {tempChar = inputText.charAt(i);tempCharIndex = (int) tempChar;//System.out.print("" + tempCharIndex + " ");tempCharCounts[tempCharIndex]++;}// Of for// 2.决定长度alphabetLength = 0;for (int i = 0; i < 255; i++) {if (tempCharCounts[i] > 0) {alphabetLength++;}// Of if}// Of for// 3.生成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 按ASCII正序alphabet[tempCounter] = (char) i;// alphabet对应的字符出现的次数charCounts[tempCounter] = tempCharCounts[i];// ASCII在alphabet中的索引charMapping[i] = tempCounter;tempCounter++;}// Of if}// Of forSystem.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/*** 建树*/public void contrastTree() {// 1.开辟空间nodes = new HuffmanNode[alphabetLength * 2 - 1];boolean[] tempProcessed = new boolean[alphabetLength * 2 - 1];// 2.生成节点们for (int i = 0; i < alphabetLength; i++) {nodes[i] = new HuffmanNode(alphabet[i], charCounts[i], null, null, null);}// Of for// 3.建树int tempLeft, tempRight, tempMinimal;for (int i = alphabetLength; i < 2 * alphabetLength - 1; i++) {// 3.1 找最小的作为左子树tempLeft = this.getMinPos(tempProcessed, i);// 3.2 找第二小的作为右子树tempRight = this.getMinPos(tempProcessed, i);System.out.println("Selecting " + tempLeft + " and " + tempRight);// 3.3 生成新的父节点charCounts[i] = charCounts[tempLeft] + charCounts[tempRight];nodes[i] = new HuffmanNode('*', charCounts[i], nodes[tempLeft], nodes[tempRight], null);// 3.4 链接nodes[tempLeft].parent = nodes[i];nodes[tempRight].parent = nodes[i];System.out.println("The children of " + i + " are " + tempLeft + " and " + tempRight);}// Of for}// Of contrastTree/*** 找权最小的节点** @param paraProcessed 标记数组，标记已经被选过的* @param paraLimit     查找范围的最大值* @return 权最小节点在charCounts[]中的下标*/public int getMinPos(boolean[] paraProcessed, int paraLimit) {int tempRes = -1;int tempMinimal = Integer.MAX_VALUE;for (int j = 0; j < paraLimit; j++) {if (paraProcessed[j]) {continue;}// Of ifif (tempMinimal > charCounts[j]) {tempMinimal = charCounts[j];tempRes = j;}// Of if}// Of for jparaProcessed[tempRes] = true;return tempRes;}// Of getMinPos/*** 获取根节点** @return 根节点*/public HuffmanNode getRoot() {return nodes[nodes.length - 1];}/*** 先序遍历霍夫曼树** @param paraNode 起始节点*/public void preOrderVisit(HuffmanNode paraNode) {System.out.println("(" + paraNode.character + " , " + paraNode.weight + ")");if (paraNode.leftChild != null) {preOrderVisit(paraNode.leftChild);}if (paraNode.rightChild != null) {preOrderVisit(paraNode.rightChild);}}/*** 生成编码 生成如：T 01000*/public void generateCodes() {huffmanCodes = new String[alphabetLength];// 单节点if (alphabetLength == 1) {System.out.println("The code of " + alphabet[0] + " is " + "1");} else {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 while// tempCharCode : 00110huffmanCodes[i] = tempCharCode;System.out.println("The code of " + alphabet[i] + " is " + tempCharCode);}// Of for}// Of if}// Of generateCodes/*** 生成字符串的编码，如果文件中不存在该字符串，输出not exist** @param paraString 字符串* @return 编码*/public String coding(String paraString) {String resultCodeString = "";int tempIndex;for (int i = 0; i < paraString.length(); i++) {// 获取ASCIItempIndex = charMapping[(int) paraString.charAt(i)];// 防止越界if (tempIndex == -1) {//System.out.println("Not exist");return "Not exist";}// Of if// 编码resultCodeString += huffmanCodes[tempIndex];} // Of for ireturn resultCodeString;}// Of coding/*** 单节点的解码** @param paraString 编码* @return 解码结果*/public String decodingSingle(String paraString) {String res = "";char tempValue = getRoot().character;for (int i = 0; i < paraString.length(); i++) {char tempChar = paraString.charAt(i);if (tempChar != '0' && tempChar != '1') {return "Invalid input";} else {if (tempChar == '1') {res += tempValue;} else {System.out.println("extra input:" + paraString.substring(i));break;}// Of if}// Of if}// Of forreturn res;}// Of decodingSingle/*** 解码* * @param paraString 给定的编码* @return 解码结果字符串*/public String decoding(String paraString) {// 单节点情况if (this.alphabetLength == 1) {return decodingSingle(paraString);}// Of ifString resString = "";HuffmanNode tempNode = getRoot();int tempMark = 0;for (int i = 0; i < paraString.length(); i++) {char tempChar = paraString.charAt(i);// 只接受0,1if (tempChar != '0' && tempChar != '1') {return "Invalid input";} else {if (tempChar == '0') {tempNode = tempNode.leftChild;} else {tempNode = tempNode.rightChild;}// Of if// 到叶节点(是初始节点，有值)if (tempNode.leftChild == null) {resString += tempNode.character;tempMark = i; // 记录上一个完成解码的位置// 防止刚好无多余编码的时候 输出多余编码时越界if (i != paraString.length() - 1) {tempNode = getRoot();}// Of if}// Of if}// Of if}// Of for// 有多余编码if (tempNode.leftChild != null) {System.out.println("extra input:" + paraString.substring(tempMark + 1));}// Of ifreturn resString;}// Of decodingpublic static void main(String[] args) {Huffman huffman = new Huffman("E:\\Master\\Day90\\src\\files\\singleLetter");huffman.constructAlphabet();huffman.contrastTree();//huffman.preOrderVisit(huffman.getRoot());huffman.generateCodes();System.out.println(huffman.coding("Hello"));System.out.println(huffman.decoding("111001"));}// Of main
}// Of class Huffman

说明：decoding()方法中，增加了一些输入合法性的判断、对多余编码的输出和对单节点的处理。
generateCodes()也增加了对单节点的处理

举例：

情况1：节点数大于1
The text is:
aaaaabbcdThe alphabet is: [a, b, c, d]
Their counts are: [5, 2, 1, 1, 0, 0, 0]The code of a is 1
The code of b is 00
The code of c is 010
The code of d is 011// 测试huffman.decoding("1110010");
// 返回的字符串：aaaba (1 1 1 00 1) extra:(0)
huffman.decoding("0001");
// 返回的字符串：b (00) extra:(01)        // 不会跳过0再输出1情况2：节点数为1
The text is:
a
The alphabet is: [a]
Their counts are: [1]The code of a is 1huffman.decoding("1110010");
// 返回的字符串：aaa( 1 1 1 ) extra:(0010)

原文：日撸代码300行（21-30天，树与二叉树）_minfanphd的博客-CSDN博客

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！