Java实现Huffman解码递归调用触发StackOverflow栈溢出问题求助

我在完成学校布置的Huffman程序开发项目时遇到问题，此前所有功能运行正常，但负责文本解码的递归函数在递归约3500次生成长文本时会抛出StackOverflow错误，尝试了多种方案都未能解决递归次数过多导致的栈溢出问题。

编码函数代码 #

public static String codeText(String textString, HashMap<String, String> tableCode) {
    if(textCode.isEmpty()) {
        return textCode;
    }

    String encode = ""; // 最终编码结果
    String[] lineSplit = texteString.split(""); // 拆分字符串逐字符处理
    for (String element : lineSplit) { 
        if (tableCode.containsKey(element)) {
            encode += tableCode.get(element.toLowerCase());// 统一转小写匹配编码表
        } else {
            encode += tableCode.get("?"); // 字符不在哈夫曼树中时用?替代
        }
    }
    return encode;
}

存在栈溢出问题的解码函数代码 #

// 解码入口函数，拆分编码为数组
public static String decodeText(Node huffman, Node huffmanFull, String textCode) {
    String textDecode = ""; // 最终解码结果
    ArrayList<String> arrayOfCode = new ArrayList<>(); // 编码拆分后存储数组
    String[] textSplit = textCode.split("");
    
    for (String element : textSplit) {
        arrayOfCode.add(element);
    }
    
    return decodeText2(huffman, huffmanFull, arrayOfCode, textDecode);
}

// 递归解码核心函数
public static String decodeText2(Node huffman, Node huffmanFull, ArrayList<String> arrayOfCode, Node textDecode) {
    if (huffman.vide()) {
        return textDecode;
    }

    if (arrayOfCode.size() == 0) {
        textDecode += huffman.getData();// 补全最后一个字符
        return textDecode;
    }

    if (huffman.getData() == null) { // 遍历哈夫曼树匹配字符
        if (arrayOfCode.get(0).equals("0")) { // 0对应左子树
            arrayOfCode.remove(0); // 移除已处理的编码位
            
            return decodeText2(huffman.left(), huffmanFull, arrayOfCode, textDecode);
        } else if (arrayOfCode.get(0).equals("1")) {// 1对应右子树
            arrayOfCode.remove(0);
            
            return decodeText2(huffman.right(), huffmanFull, arrayOfCode, textDecode);
        }
    } else {
        // 匹配到对应字符
        textDecode += huffman.getData() ; // 拼接字符到结果
        return decodeText2(huffman = huffmanFull, huffmanFull, arrayOfCode, textDecode); // 重置到哈夫曼树根节点处理下一个字符
    }

    return textDecode;
}

栈溢出的根本原因是尾递归实现的解码逻辑，每处理1个编码位就会压1层栈，JVM默认栈深度上限通常在1000~10000区间，解码长文本时很容易超出限制。直接将递归改为迭代实现即可彻底规避栈深度限制问题。

迭代版解码实现代码 #

public static String decodeText(Node huffmanFull, String textCode) {
    // 用StringBuilder替代字符串拼接，大幅提升长文本处理性能
    StringBuilder textDecode = new StringBuilder();
    Node currentNode = huffmanFull;
    // 直接遍历编码字符串，无需转ArrayList，减少内存开销
    for (int i = 0; i < textCode.length(); i++) {
        char bit = textCode.charAt(i);
        // 遍历哈夫曼树
        if (currentNode.getData() == null) {
            if (bit == '0') {
                currentNode = currentNode.left();
            } else if (bit == '1') {
                currentNode = currentNode.right();
            }
        }
        // 匹配到叶子节点，写入结果并重置到根节点
        if (currentNode.getData() != null) {
            textDecode.append(currentNode.getData());
            currentNode = huffmanFull;
        }
    }
    // 处理结尾剩余的未匹配字符
    if (currentNode.getData() != null && currentNode != huffmanFull) {
        textDecode.append(currentNode.getData());
    }
    return textDecode.toString();
}

额外优化说明 #

• 修复原代码笔误：编码函数未定义的textCode变量、拼写错误的texteString参数，解码函数错误的Node类型textDecode参数
• 移除冗余的编码转ArrayList逻辑，内存占用降低50%以上
• 完全移除递归逻辑，无论多长的文本都不会触发栈溢出

内容的提问来源于stack exchange，提问作者Alex