java - 在二叉树中找到一个值避免计算器异常

Question

我试图在二叉树中找到一个值并返回具有我要查找的值的节点。

我做了一个算法，当值不在树的很深层次时效果很好，但是当值在很深的位置时，我得到一个 java.lang.StackOverflowError。这是我的代码:

class Nope {
    
    Nope left, right;
    int value;

    public Nope find(int v){
        if(v > this.value && this.right != null)
            return right.find(v);
        if(v < this.value && this.left != null)
            return left.find(v);
        if(this.value == v)
            return this;
        return null;
    }
}

任何人都可以建议我解决这个问题(我听说过尾优化递归之类的东西)但我不确定它是否适用于 Java。

Answer 1

最简单的方法是将其转换为 while 循环，它只维护“我们正在测试的当前节点”的状态。

在循环的每次迭代中，存在三种可能性:

• 当前节点有正确的值，此时可以返回
• 当前节点在正确的“边”有一个子节点，在这种情况下，您可以继续迭代该子节点作为新的“当前节点”
• 以上两种情况都不是，在这种情况下找不到值，可以返回null

所以像这样:

public Nope find(int v) {
    Nope current = this;
    while (current != null) {
        if (current.value == v) {
            return current;
        }
        // This will drop out of the loop naturally if there's no appropriate subnode
        current = v < current.value ? current.left : current.right;
    }
    return null;
}

或者代码更少，但可读性可能更差:

public Nope find(int v) {
    Nope current = this;
    // Keep navigating down the tree until either we've run
    // out of nodes to look at, or we've found the right value.
    while (current != null && current.value != v) {
        current = v < current.value ? current.left : current.right;
    }
    return current;
}