java - 在二叉搜索树中查找父节点

Question

这是在二叉搜索树中查找父节点的代码。我无法理解它是如何工作的，因为除了 null 之外，我们从来没有为父级分配任何值。我是递归的新手。

public Node findParent(Type data) 
{
    return findParent(data, root, null);
}

public Node findParent(Type x, Node node, Node parent) 
{
    if (node == null) {
        return null;
    } else if (!(node.data == x)) {
        parent = findParent(x, node.left, node);
        if (parent == null) {
            parent = findParent(x, node.right, node);
        }
    }
    return parent;
}

Answer 1

您在递归调用中为父级分配了一个非空值:

parent = findParent(x, node.left, node);
                                  ----
parent = findParent(x, node.right, node);
                                   ----

parent 仅在初始调用中为空(因为树的根没有父级)。

每次调用 findParent 都会得到一个值 (x)、一个节点 (node) 和该节点的父节点 ( > parent )。如果在 Node 中找到该值，则返回 parent，否则，您在左子树中搜索该值，如果仍未找到，则在右子树中搜索它。