Блог

Я пытаюсь написать функцию декодирования дерева Хаффмана для декодирования заданного логического массива.Я использую метод рекурсии в 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 amp;amp; 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);
        }
    }
}
 

Проблема в том, что вы инициализируете int i = 0 внутри decode_helper метода. И этот метод вызывается рекурсивно. Поскольку i она всегда инициализируется нулем, она никогда не станет равной coding.length и, следовательно, бесконечному циклу.

Возможно, вам потребуется инициализировать i вне decode_helper метода и передать его внутри него.