在二叉树中查找值,避免堆栈溢出异常

Question

我试图在二叉树中找到一个值并返回具有我正在寻找的值的节点.

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

class Node {

    // keep these??????????????????????????????? fields
    Node left, right;
    int value;

    public Node 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循环,它只保持"我们正在测试的当前节点"的状态.

在循环的每次迭代中,有三种可能性:

• 当前节点具有正确的值,在这种情况下您可以返回它
• 当前节点在正确的"side"上有一个子节点,在这种情况下,您可以继续使用该子节点作为新的"当前节点"进行迭代
• 以上都不是这种情况,在这种情况下找不到值,您可以返回null

所以类似于:

public Node find(int v) {
    Node 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 Node find(int v) {
    Node 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;
}

Answer 2

您的代码重新编译为迭代的示例:

class Node {

    // keep these??????????????????????????????? fields
    Node left, right;
    int value;

    public Node find(int v){
        Node n = this;

        while (n != null)
        {
            if (v > n.value)
                n = n.right;
            else if (v < n.value)
                n = n.left;
            else // v == n.value
                return n;
        }

        return null;
    }
}

编辑:只是一个关于它是如何工作的说明,以防它不清楚.由于您永远不需要记住有关如何到达当前节点的任何信息,因此我们只跟踪我们需要搜索的当前子树的根.在每一步,我们要么确定没有剩下要搜索的子树(第一个条件),左边或右边可能有一个子树(中间两个条件),或者我们实际上已经找到了根的子树.当前子树(最后条件).我们继续寻找,直到我们用完子树(条件),如果我们用完了,我们知道值不在树中,我们返回null.

编辑:正如评论中指出的那样,使用连续的ifs是个问题.我已经更新了代码以使用if/else if/else.