Я пытаюсь написать функцию декодирования дерева Хаффмана для декодирования заданного логического массива. Я использую метод рекурсии в decode_helper (), но продолжаю попадать в бесконечный цикл, и я не уверенпочему, потому что я думал, что реализовал правильный базовый случай, чтобы остановить рекурсивные вызовы.
Я пытался поиграть с различными базовыми сценариями, но ничего, что я пытаюсь сделать, кажется, не останавливает рекурсивные вызовы.
public class HuffmanTree {
public class HuffmanTree {
// ******************** Start of Stub Code ******************** //
// ************************************************************ //
/** Node<E> is an inner class and it is abstract.
* There will be two kinds
* of Node, one for leaves and one for internal nodes. */
abstract static class Node implements Comparable<Node>{
/** The frequency of all the items below this node */
protected int frequency;
public Node(int freq) {
this.frequency = freq;
}
/** Needed for the Minimum Heap used later in this stub. */
public int compareTo(Node other) {
return this.frequency - other.frequency;
}
}
/** Leaves of a Huffman tree contain the data items */
protected static class LeafNode extends Node {
// Data Fields
/** The data in the node */
protected char data;
/** Constructor to create a leaf node (i.e. no children) */
public LeafNode(char data, int freq) {
super(freq);
this.data = data;
}
/** toString method */
public String toString() {
return "[value= "+this.data + ",freq= "+frequency+"]";
}
}
/** Internal nodes contain no data,
* just references to left and right subtrees */
protected static class InternalNode extends Node {
/** A reference to the left child */
protected Node left;
/** A reference to the right child */
protected Node right;
/** Constructor to create an internal node */
public InternalNode(Node leftC, Node rightC) {
super(leftC.frequency + rightC.frequency);
left = leftC; right = rightC;
}
public String toString() {
return "(freq= "+frequency+")";
}
}
// Enough space to encode all "extended ascii" values
// This size is probably overkill (since many of the values are not
//"printable" in the usual sense)
private static final int codex_size = 256;
/* Data Fields for Huffman Tree */
private Node root;
public HuffmanTree(String s) {
root = buildHuffmanTree(s);
}
/**
* Returns the frequencies of all characters in s.
* @param s
* @return
*/
//How many times a character shows up in a string
public static int[] frequency(String s) {
int[] freq = new int[codex_size];
for (char c: s.toCharArray()) {
freq[c]++;
}
return freq;
}
public String decode(boolean[] coding) {
// TODO Complete decode method
//Function to decode the binary input
String code = "";
Node temp = root;
int i = 0;
if (coding.length == 0) {
throw new IllegalArgumentException("The given code cannot be empty");
}
for(int j = 0; j < coding.length; j++) {
if(coding[j] != true && coding[j] != false) {
throw new IllegalArgumentException("The given code has an invalid
input");
}
}
decode_helper(temp, code, coding);
return code;
}
public void decode_helper(Node root, String code, boolean[] coding) {
int i = 0;
if(root == null) {
throw new IllegalArgumentException("Given tree is empty");
}
//Base case for the recursion
if(i != coding.length) {
if (root instanceof InternalNode) {
InternalNode n = (InternalNode)root;
if(coding[i] == false) {
n.left = (InternalNode)root;
i++;
decode_helper(n.left, code, coding);
}
if(coding[i] == true) {
n.right = (InternalNode)root;
i++;
decode_helper(n.right, code, coding);
}
}
else if (root instanceof LeafNode) {
LeafNode l = (LeafNode)root;
code += l.data;
i++;
decode_helper(root, code, coding);
}
}
}