java - 在树中递归搜索时出现 Stackoverflow 错误

Question

我正在使用 Java 实现 Shannon/Fano 算法，我通过计算文本文件中符号的频率来实现此目的，然后将所有这些值放入树中。问题是，当我在树中搜索某个符号时，我还必须更新相应符号的代码(例如，如果我转到左侧追加 0，否则为 1)，并且递归地执行此操作，我会收到 stackoverflow 错误。下面是我的代码:

private String getNodeValue(Node node, String symbol) {
    if (node.getLeftChild() != null) {
        if (node.getLeftChild().getData().equalsIgnoreCase(symbol)) {
            node.updateCode(0);
            return node.getData() + "";
        }
    } else if (node.getRightChild() != null) {
        if (node.getRightChild().getData().equalsIgnoreCase(symbol)) {
            node.updateCode(1);
            return node.getData() + "";
        }
    }


    Node nextLeftNode = node.getLeftChild().getLeftChild();
    if (nextLeftNode != null) {
        getNodeValue(nextLeftNode, symbol);
    }

    Node nextRightNode = node.getRightChild().getRightChild();
    if (nextRightNode != null) {
        getNodeValue(nextRightNode, symbol);
    }

    // if symbol is not found return null
    return null;
}

当调用 node.getData() 时，会在该方法的第一行触发 stackoverflow 错误。这是我的堆栈跟踪:

Exception in thread "main" java.lang.StackOverflowError
at ro.uvt.it.datastractures.Node.getData(Node.java:47)
at ro.uvt.it.datastractures.Node.getData(Node.java:47)
at ro.uvt.it.datastractures.Node.getData(Node.java:47)

这是我的 getData() 方法:

public String getData() {
    return this.getData();
}

任何帮助或提示将不胜感激，谢谢。

Answer 1

您的代码中有很多错误。

正如您在堆栈跟踪中所示，无限递归位于 getData 方法中，而不是在 getNodeValue 方法中，因此您需要发布 getData 方法的源代码。

但是 getNodeValue 方法也有很多错误。

前两个 if 语句具有完全相同的条件:

if (node.getData().equalsIgnoreCase(symbol)) {

和

else if (((String) node.getData()).equalsIgnoreCase(symbol)) {

这些 if 语句中的 return 将一个空字符串附加到已返回 String 的 getData() 结果中。将它们分别替换为:

return node.getData();

只是一种不同的编写方式，因为 getData() 已经返回一个 String，因此再次转换为 String 不会产生任何影响。

接下来的 if 语句会递归调用 leftChild 和 rightChild 上的 getNodeValue，但它们不会返回任何内容，因此一旦您的方法中经过了前两个相同的 if 语句，您最终总是会在代码中返回 null。

您的代码可能应该阅读:

if (node.getLeftChild() != null) {
    String found = getNodeValue(node.getLeftChild(), symbol);
    if (found != null) {
        return found;
    }
}
if (node.getRightChild() != null) {
    String found = getNodeValue(node.getRightChild(), symbol);
    if (found != null) {
        return found;
    }
}